Complexity and Kernels for Bipartition into Degree-bounded Induced Graphs

DOI10.1007/978-3-319-13075-0_34zbMath1432.68197OpenAlexW321045186MaRDI QIDQ2942649

Hiroshi Nagamochi, Mingyu Xiao

Publication date: 11 September 2015

Published in: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-13075-0_34

Mathematics Subject Classification ID

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) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (5)

Faster Computation of the Maximum Dissociation Set and Minimum 3-Path Vertex Cover in Graphs ⋮ Kernelization of edge perfect code and its variants ⋮ Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems ⋮ Complexity and kernels for bipartition into degree-bounded induced graphs ⋮ Exact algorithms for dominating induced matching based on graph partition

Cites Work

• Unnamed Item
• Unnamed Item
• 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
• Degree-constrained decompositions of graphs: Bounded treewidth and planarity
• An O *(1.1939 n ) Time Algorithm for Minimum Weighted Dominating Induced Matching
• 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