The parameterized complexity of editing graphs for bounded degeneracy
DOI10.1016/J.TCS.2010.05.015zbMATH Open1207.05200OpenAlexW1980876266MaRDI QIDQ986553FDOQ986553
Authors: Luke Mathieson 
Publication date: 11 August 2010
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2010.05.015
Recommendations
computational complexityparameterized complexitycombinatorial problemsgraph editingdegenerate graphs
Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Structural characterization of families of graphs (05C75)
Cites Work
- Parameterized complexity of finding regular induced subgraphs
- The extremal function for complete minors
- Parametrized complexity theory.
- Title not available (Why is that?)
- k-Degenerate Graphs
- Lower bound of the Hadwiger number of graphs by their average degree
- Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues
- Title not available (Why is that?)
- Title not available (Why is that?)
- Nondeterminism within $P^ * $
- Deciding first-order properties of locally tree-decomposable structures
- Title not available (Why is that?)
- Linear Time Algorithms for Finding a Dominating Set of Fixed Size in Degenerated Graphs
- Parameterized Graph Editing with Chosen Vertex Degrees
- Backdoor sets for DLL subsolvers
- Machine-based methods in parameterized complexity theory
- Parameterized Complexity for Domination Problems on Degenerate Graphs
Cited In (14)
- A parameterized complexity view on collapsing \(k\)-cores
- Degree-constrained orientation of maximum satisfaction: graph classes and parameterized complexity
- On the complexity of target set selection in simple geometric networks
- Title not available (Why is that?)
- Establishing herd immunity is hard even in simple geometric networks
- Parameterized orientable deletion
- A survey of parameterized algorithms and the complexity of edge modification
- Parameterized complexity of three edge contraction problems with degree constraints
- Circulant graphs and GCD and LCM of subsets
- Title not available (Why is that?)
- Graph editing to a given neighbourhood degree list is fixed-parameter tractable
- Incremental problems in the parameterized complexity setting
- Title not available (Why is that?)
- Graph editing problems with extended regularity constraints
This page was built for publication: The parameterized complexity of editing graphs for bounded degeneracy
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q986553)
