Editing to a Planar Graph of Given Degrees

DOI10.1007/978-3-319-20297-6_10zbMath1356.68095arXiv1508.02773OpenAlexW2743518277MaRDI QIDQ3194713

Konrad K. Dabrowski, Pim van 't Hof, Daniël Paulusma, Dimitrios M. Thilikos, Petr A. Golovach

Publication date: 20 October 2015

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

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 (3)

Graph editing to a given degree sequence ⋮ Graph Editing to a Given Degree Sequence ⋮ Editing to a planar graph of given degrees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• Parameterized complexity of even/odd subgraph problems
• Parameterized complexity of finding regular induced subgraphs
• The node-deletion problem for hereditary properties is NP-complete
• Deciding whether a planar graph has a cubic subgraph is NP-complete
• 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
• Editing to a Connected Graph of Given Degrees
• Win-Win Kernelization for Degree Sequence Completion Problems
• The Planar Hamiltonian Circuit Problem is NP-Complete
• The spanning subgraphs of eulerian graphs
• Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions
• (Meta) Kernelization
• Node-and edge-deletion NP-complete problems
• Complexity classification of some edge modification problems

This page was built for publication: Editing to a Planar Graph of Given Degrees