Complexity and kernels for bipartition into degree-bounded induced graphs

DOI10.1016/j.tcs.2016.11.011zbMath1355.68131OpenAlexW2555985695MaRDI QIDQ730002

Hiroshi Nagamochi, Mingyu Xiao

Publication date: 23 December 2016

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2016.11.011

zbMATH Keywords

NP-hardgraph algorithmsbipartitionkernelizationfixed-parameter tractable

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (6)

An efficient polynomial time approximation scheme for the vertex cover \(P_3\) problem on planar graphs ⋮ On the kernelization of split graph problems ⋮ Vertex partitioning problems on graphs with bounded tree width ⋮ Degree-constrained 2-partitions of graphs ⋮ The \((3, 3)\)-colorability of planar graphs without 4-cycles and 5-cycles ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• On a generalization of Nemhauser and Trotter's local optimization theorem
• Parameterized complexity of finding small degree-constrained subgraphs
• A generalization of Nemhauser and Trotter's local optimization theorem
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• On bounded-degree vertex deletion parameterized by treewidth
• Efficient algorithms for decomposing graphs under degree constraints
• Parameterized complexity of finding regular induced subgraphs
• Efficient edge domination problems in graphs
• Exact algorithms for dominating induced matching based on graph partition
• Degree-constrained decompositions of graphs: Bounded treewidth and planarity
• Complexity and Kernels for Bipartition into Degree-bounded Induced Graphs
• Recognizing decomposable graphs
• On decomposition of triangle-free graphs under degree constraints
• Decomposing graphs with girth at least five under degree constraints
• Algorithms and Computation

This page was built for publication: Complexity and kernels for bipartition into degree-bounded induced graphs