Parameterized Graph Editing with Chosen Vertex Degrees

DOI10.1007/978-3-540-85097-7_2zbMath1168.68445OpenAlexW1513702025MaRDI QIDQ5505639

Luke Mathieson, Stefan Szeider

Publication date: 27 January 2009

Published in: Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-85097-7_2

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)

Related Items

Editing graphs to satisfy degree constraints: a parameterized approach ⋮ Unnamed Item ⋮ The parameterized complexity of editing graphs for bounded degeneracy ⋮ Parameterized complexity of finding regular induced subgraphs

Cites Work

• Unnamed Item
• Unnamed Item
• The complexity of regular subgraph recognition
• On the fixed-parameter tractability of parameterized model-checking problems
• Parameterized complexity of finding regular induced subgraphs
• A note on the complexity of finding regular subgraphs
• Matching theory
• Deciding whether a planar graph has a cubic subgraph is NP-complete
• Fixed-parameter tractability of graph modification problems for hereditary properties
• On locating cubic subgraphs in bounded-degree connected bipartite graphs
• Finding a \(\Delta\)-regular supergraph of minimum order
• Finding regular subgraphs in both arbitrary and planar graphs
• Parametrized complexity theory.
• Approximating Element-Weighted Vertex Deletion Problems for the Complete k-Partite Property
• Deciding first-order properties of locally tree-decomposable structures
• The Cluster Editing Problem: Implementations and Experiments
• Paths, Trees, and Flowers
• Three‐regular subgraphs of four‐regular graphs