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

zbMATH Keywords

computational complexityparameterized complexitycombinatorial problemsgraph editingdegenerate graphs

Mathematics Subject Classification ID

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)

Recommendations

• Editing graphs to satisfy degree constraints: a parameterized approach
• Parameterized Graph Editing with Chosen Vertex Degrees
• Graph editing to a given degree sequence
• Graph editing to a given degree sequence
• Edge-editing to a dense and a sparse graph class

Cites work

• scientific article; zbMATH DE number 5485529 (Why is no real title available?)
• scientific article; zbMATH DE number 1025912 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 806748 (Why is no real title available?)
• k-Degenerate Graphs
• Backdoor sets for DLL subsolvers
• Deciding first-order properties of locally tree-decomposable structures
• Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues
• Linear Time Algorithms for Finding a Dominating Set of Fixed Size in Degenerated Graphs
• Lower bound of the Hadwiger number of graphs by their average degree
• Machine-based methods in parameterized complexity theory
• Nondeterminism within $P^ * $
• Parameterized Complexity for Domination Problems on Degenerate Graphs
• Parameterized Graph Editing with Chosen Vertex Degrees
• Parameterized complexity of finding regular induced subgraphs
• Parametrized complexity theory.
• The extremal function for complete minors

Cited in

(15)

• Parameterized complexity of three edge contraction problems with degree constraints
• Edge-editing to a dense and a sparse graph class
• A parameterized complexity view on collapsing \(k\)-cores
• A parameterized complexity view on collapsing \(k\)-cores
• On the complexity of target set selection in simple geometric networks
• Establishing herd immunity is hard even in simple geometric networks
• Parameterized orientable deletion
• Parameterized orientable deletion
• Graph editing to a given neighbourhood degree list is fixed-parameter tractable
• A survey of parameterized algorithms and the complexity of edge modification
• Degree-constrained orientation of maximum satisfaction: graph classes and parameterized complexity
• Incremental problems in the parameterized complexity setting
• scientific article; zbMATH DE number 7525474 (Why is no real title available?)
• Graph editing problems with extended regularity constraints
• Circulant graphs and GCD and LCM of subsets

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)