Graph editing problems with extended regularity constraints

DOI10.1016/j.tcs.2017.03.019zbMath1370.68137arXiv1510.03482OpenAlexW2242403838MaRDI QIDQ526874

Luke Mathieson

Publication date: 15 May 2017

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

computational complexitygraph algorithmsparameterized complexitygraph editing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (3)

Fixed-parameter tractable distances to sparse graph classes ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Editing to a planar graph of given degrees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph isomorphism parameterized by elimination distance to bounded degree
• Fundamentals of parameterized complexity
• Editing graphs to satisfy degree constraints: a parameterized approach
• Parameterized complexity of three edge contraction problems with degree constraints
• Editing to a planar graph of given degrees
• Looking at the stars
• The complexity of regular subgraph recognition
• The parameterized complexity of editing graphs for bounded degeneracy
• Parameterized complexity of finding regular induced subgraphs
• On problems without polynomial kernels
• A note on the complexity of finding regular subgraphs
• General factors of graphs
• The polynomial-time hierarchy
• Deciding whether a planar graph has a cubic subgraph is NP-complete
• On locating cubic subgraphs in bounded-degree connected bipartite graphs
• Finding a \(\Delta\)-regular supergraph of minimum order
• Spanning subgraphs with specified valencies
• Finding regular subgraphs in both arbitrary and planar graphs
• Editing to a graph of given degrees
• Maximum \(k\)-regular induced subgraphs
• Tractable cases of the extended global cardinality constraint
• Parametrized complexity theory.
• Editing to a Connected Graph of Given Degrees
• Win-Win Kernelization for Degree Sequence Completion Problems
• Deciding first-order properties of locally tree-decomposable structures
• Paths, Trees, and Flowers
• On the completeness of a generalized matching problem
• Maximum matching and a polyhedron with 0,1-vertices
• The factorization of graphs. II
• A Short Proof of the Factor Theorem for Finite Graphs
• Combinatorial optimization. Theory and algorithms.

This page was built for publication: Graph editing problems with extended regularity constraints