Editing to a planar graph of given degrees
From MaRDI portal
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)
Recommendations
Cites work
- scientific article; zbMATH DE number 2234775 (Why is no real title available?)
- (Meta) kernelization
- A Short Proof of the Factor Theorem for Finite Graphs
- A \(c^k n\) 5-approximation algorithm for treewidth
- A linear kernel for planar red-blue dominating set
- Complexity classification of some edge modification problems
- Deciding whether a planar graph has a cubic subgraph is NP-complete
- Editing graphs to satisfy degree constraints: a parameterized approach
- Editing to Eulerian graphs
- Editing to a connected graph of given degrees
- Editing to a planar graph of given degrees
- Efficient Planarity Testing
- Explicit linear kernels via dynamic programming
- Fixed-parameter tractability of graph modification problems for hereditary properties
- Fundamentals of parameterized complexity
- Graph editing problems with extended regularity constraints
- Linear kernels for (connected) dominating set on \(H\)-minor-free graphs
- Matching theory
- NP-completeness results for edge modification problems
- Node-and edge-deletion NP-complete problems
- Parameterized complexity of Eulerian deletion problems
- Parameterized complexity of even/odd subgraph problems
- Parameterized complexity of finding regular induced subgraphs
- Parameterized complexity of finding subgraphs with hereditary properties.
- Parameterized complexity of three edge contraction problems with degree constraints
- Parametrized complexity theory.
- The Planar Hamiltonian Circuit Problem is NP-Complete
- The node-deletion problem for hereditary properties is NP-complete
- The spanning subgraphs of eulerian graphs
- Treewidth. Computations and approximations
- Win-win kernelization for degree sequence completion problems
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
- Win-win kernelization for degree sequence completion problems
- Editing to Connected F-Degree Graph
- 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)
