Parameterized complexity of even/odd subgraph problems

DOI10.1016/j.jda.2011.03.004zbMath1225.05228WikidataQ114162510 ScholiaQ114162510MaRDI QIDQ635735

Boting Yang, Leizhen Cai

Publication date: 23 August 2011

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2011.03.004

zbMATH Keywords

Eulerian graphs; parameterized complexity; color-coding; odd graphs; FPT algorithms; even graphs; random separation

Mathematics Subject Classification ID

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Graph Editing to a Given Degree Sequence, On the complexity of finding large odd induced subgraphs and odd colorings, A survey of parameterized algorithms and the complexity of edge modification, Parameterized complexity of connected even/odd subgraph problems, Graph editing to a given degree sequence, Parameterized complexity of even/odd subgraph problems, Editing to a planar graph of given degrees, Editing to Eulerian graphs, Finding even subgraphs even faster, A new view on rural postman based on Eulerian extension and matching, Editing to a graph of given degrees, Parameterized complexity of Eulerian deletion problems, Plane augmentation of plane graphs to meet parity constraints, Editing to a Planar Graph of Given Degrees

Cites Work

• Parameterized complexity of even/odd subgraph problems
• On problems without polynomial kernels
• The node-deletion problem for hereditary properties is NP-complete
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Parameterized complexity of finding subgraphs with hereditary properties.
• The Spatial Complexity of Oblivious k-Probe Hash Functions
• Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems
• Color-coding
• The Parametrized Complexity of Some Fundamental Problems in Coding Theory
• Complexity classification of some edge modification problems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item