The parameterized complexity of editing graphs for bounded degeneracy

DOI10.1016/j.tcs.2010.05.015zbMath1207.05200OpenAlexW1980876266MaRDI QIDQ986553

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 complexitycombinatorial problemsdegenerate graphsparameterized complexitygraph editing

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

A parameterized complexity view on collapsing \(k\)-cores ⋮ Parameterized orientable deletion ⋮ Establishing herd immunity is hard even in simple geometric networks ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Unnamed Item ⋮ Parameterized complexity of three edge contraction problems with degree constraints ⋮ Circulant graphs and GCD and LCM of subsets ⋮ Incremental problems in the parameterized complexity setting ⋮ Graph editing problems with extended regularity constraints ⋮ Unnamed Item ⋮ Degree-constrained orientation of maximum satisfaction: graph classes and parameterized complexity ⋮ Unnamed Item

Cites Work

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