Editing to a planar graph of given degrees
DOI10.1016/J.JCSS.2016.11.009zbMATH Open1356.68096OpenAlexW1913638054MaRDI QIDQ730508FDOQ730508
Konrad 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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Planar graphs; geometric and topological aspects of graph theory (05C10)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Fundamentals of parameterized complexity
- Matching theory
- Fixed-parameter tractability of graph modification problems for hereditary properties
- Parameterized complexity of finding regular induced subgraphs
- The node-deletion problem for hereditary properties is NP-complete
- Parametrized complexity theory.
- Efficient Planarity Testing
- The Planar Hamiltonian Circuit Problem is NP-Complete
- Node-and edge-deletion NP-complete problems
- Treewidth. Computations and approximations
- The spanning subgraphs of eulerian graphs
- Editing to a graph of given degrees
- Editing to a Connected Graph of Given Degrees
- Win-win kernelization for degree sequence completion problems
- Editing graphs to satisfy degree constraints: a parameterized approach
- A Short Proof of the Factor Theorem for Finite Graphs
- Complexity classification of some edge modification problems
- Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions
- NP-completeness results for edge modification problems
- Editing to Eulerian graphs
- Deciding whether a planar graph has a cubic subgraph is NP-complete
- Parameterized complexity of finding subgraphs with hereditary properties.
- Parameterized complexity of even/odd subgraph problems
- Parameterized complexity of three edge contraction problems with degree constraints
- A \(c^k n\) 5-approximation algorithm for treewidth
- Parameterized complexity of Eulerian deletion problems
- Editing to a Planar Graph of Given Degrees
- Explicit Linear Kernels via Dynamic Programming
- A linear kernel for planar red-blue dominating set
- Graph editing problems with extended regularity constraints
- (Meta) Kernelization
Cited In (5)
This page was built for publication: Editing to a planar graph of given degrees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q730508)
