Parameterized complexity of even/odd subgraph problems
From MaRDI portal
Publication:635735
DOI10.1016/j.jda.2011.03.004zbMath1225.05228WikidataQ114162510 ScholiaQ114162510MaRDI QIDQ635735
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
Eulerian graphs; parameterized complexity; color-coding; odd graphs; FPT algorithms; even graphs; random separation
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