Editing to a planar graph of given degrees
DOI10.1016/J.JCSS.2016.11.009zbMATH Open1356.68096OpenAlexW1913638054MaRDI QIDQ730508FDOQ730508
Authors: Konrad Dabrowski, Petr A. Golovach, Pim Van 't Hof, Daniël Paulusma, 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
Recommendations
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
- 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
- Title not available (Why is that?)
- 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
- Linear kernels for (connected) dominating set on \(H\)-minor-free graphs
- (Meta) kernelization
Cited In (8)
- Editing to a connected graph of given degrees
- Win-win kernelization for degree sequence completion problems
- A survey of parameterized algorithms and the complexity of edge modification
- Graph editing to a given degree sequence
- Editing to Connected F-Degree Graph
- Win-win kernelization for degree sequence completion problems
- Editing to a planar graph of given degrees
- Graph editing problems with extended regularity constraints
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)
