Editing to a connected graph of given degrees

DOI10.1016/j.ic.2017.04.013zbMath1376.68066OpenAlexW2609477008MaRDI QIDQ2407094

Petr A. Golovach

Publication date: 28 September 2017

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2017.04.013

zbMATH Keywords

connectivityparameterized complexitydegree constraintsgraph editing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Connectivity (05C40) Vertex degrees (05C07)

Related Items

Building large \(k\)-cores from sparse graphs, A survey of parameterized algorithms and the complexity of edge modification, Unnamed Item, Editing to Connected F-Degree Graph

Cites Work

• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Editing graphs to satisfy degree constraints: a parameterized approach
• Parameterized complexity of finding regular induced subgraphs
• Matching theory
• 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.
• NP-completeness results for edge modification problems
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• Editing to Connected f-Degree Graph
• Node-and edge-deletion NP-complete problems
• Parameterized Algorithms
• Complexity classification of some edge modification problems