Parameterized Complexity of Even/Odd Subgraph Problems
Refereed conference paper presented and published in conference proceedings


Full Text

Times Cited
Web of Science1WOS source URL (as at 16/02/2021) Click here for the latest count

Other information
AbstractIn this paper, we investigate the parameterized complexity of the problem of finding k edges (vertices) in a graph G to form a subgraph (respectively, induced subgraph) H such that H belongs to one the following four classes of graphs: even graphs, Eulerian graphs, odd graphs, and connected odd graphs. We also study the parameterized complexity of their parametric dual problems. Among these sixteen problems, we show that eight of them are fixed parameter tractable and four are W[1]-hard. Our main techniques are the color-coding method of Alon, Yuster and Zwick, and the random separation method of Cai, Chan and Chan.
All Author(s) ListCai LZ, Yang BT
Name of Conference7th International Conference on Algorithms and Complexity
Start Date of Conference26/05/2010
End Date of Conference28/05/2010
Place of ConferenceRome
Country/Region of ConferenceItaly
Journal nameLecture Notes in Artificial Intelligence
Detailed descriptionTo ORKTS: Published online, volume and page numbers are yet to be assigned.
Year2010
Month1
Day1
Volume Number6078
PublisherSPRINGER-VERLAG BERLIN
Pages85 - 96
ISBN978-3-642-13072-4
ISSN0302-9743
LanguagesEnglish-United Kingdom
Web of Science Subject CategoriesComputer Science; Computer Science, Information Systems; Computer Science, Theory & Methods; Telecommunications

Last updated on 2021-17-02 at 01:30