Editing to a planar graph of given degrees
DOI10.1016/j.jcss.2016.11.009zbMath1356.68096OpenAlexW1913638054MaRDI QIDQ730508
Konrad K. Dabrowski, Pim van 't Hof, Daniël Paulusma, Petr A. Golovach, Dimitrios M. Thilikos
Publication date: 28 December 2016
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2016.11.009
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (2)
Cites Work
- Unnamed Item
- Unnamed Item
- Win-win kernelization for degree sequence completion problems
- Fundamentals of parameterized complexity
- Editing graphs to satisfy degree constraints: a parameterized approach
- Parameterized complexity of three edge contraction problems with degree constraints
- A linear kernel for planar red-blue dominating set
- Graph editing problems with extended regularity constraints
- Parameterized complexity of even/odd subgraph problems
- Editing to Eulerian graphs
- Parameterized complexity of finding regular induced subgraphs
- Matching theory
- The node-deletion problem for hereditary properties is NP-complete
- Deciding whether a planar graph has a cubic subgraph is NP-complete
- Treewidth. Computations and approximations
- 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
- Parameterized complexity of Eulerian deletion problems
- Parametrized complexity theory.
- NP-completeness results for edge modification problems
- A $c^k n$ 5-Approximation Algorithm for Treewidth
- Editing to a Connected Graph of Given Degrees
- (Meta) Kernelization
- Editing to a Planar Graph of Given Degrees
- Explicit Linear Kernels via Dynamic Programming
- Efficient Planarity Testing
- The Planar Hamiltonian Circuit Problem is NP-Complete
- The spanning subgraphs of eulerian graphs
- Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions
- Node-and edge-deletion NP-complete problems
- A Short Proof of the Factor Theorem for Finite Graphs
- Complexity classification of some edge modification problems
This page was built for publication: Editing to a planar graph of given degrees
