Parameterized complexity of even/odd subgraph problems

DOI10.1016/j.jda.2011.03.004zbMath1225.05228OpenAlexW2035543139WikidataQ114162510 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 graphsparameterized complexitycolor-codingodd graphsFPT algorithmseven graphsrandom separation

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (14)

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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

This page was built for publication: Parameterized complexity of even/odd subgraph problems