Editing to a graph of given degrees

DOI10.1016/j.tcs.2015.04.034zbMath1322.68142arXiv1311.4768OpenAlexW1577575477MaRDI QIDQ2354405

Petr A. Golovach

Publication date: 13 July 2015

Published in: Theoretical Computer Science, Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1311.4768

zbMATH Keywords

parameterized complexitygraph editinggraphs of given degrees

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex degrees (05C07)

Related Items (13)

Win-win kernelization for degree sequence completion problems ⋮ Editing to a Planar Graph of Given Degrees ⋮ Fixed-parameter tractable distances to sparse graph classes ⋮ Editing to Eulerian graphs ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ A parameterized algorithmics framework for degree sequence completion problems in directed graphs ⋮ Graph editing to a given degree sequence ⋮ Graph editing problems with extended regularity constraints ⋮ Graph Editing to a Given Degree Sequence ⋮ Unnamed Item ⋮ Editing to a planar graph of given degrees ⋮ Finding large degree-anonymous subgraphs is hard ⋮ Editing to a graph of given degrees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Editing graphs to satisfy degree constraints: a parameterized approach
• Parameterized complexity of even/odd subgraph problems
• Parameterized complexity of finding regular induced subgraphs
• The node-deletion problem for hereditary properties is NP-complete
• A trinomial analogue of Bailey's lemma and \(N=2\) superconformal invariance
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Parameterized complexity of finding subgraphs with hereditary properties.
• Editing to a graph of given degrees
• Additive approximation for edge-deletion problems
• Parametrized complexity theory.
• NP-completeness results for edge modification problems
• Editing to a Connected Graph of Given Degrees
• Parameterized Complexity of Eulerian Deletion Problems
• Win-Win Kernelization for Degree Sequence Completion Problems
• Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems
• Color-coding
• Kernelization Lower Bounds by Cross-Composition
• Node-and edge-deletion NP-complete problems
• Complexity classification of some edge modification problems

This page was built for publication: Editing to a graph of given degrees