Complexity and kernels for bipartition into degree-bounded induced graphs
DOI10.1016/J.TCS.2016.11.011zbMATH Open1355.68131OpenAlexW2555985695MaRDI QIDQ730002FDOQ730002
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
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Cites Work
- Title not available (Why is that?)
- Parameterized complexity of finding regular induced 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 edge domination problems in graphs
- Exact algorithms for dominating induced matching based on graph partition
- Complexity and Kernels for Bipartition into Degree-bounded Induced Graphs
- On decomposition of triangle-free graphs under degree constraints
- Title not available (Why is that?)
- Decomposing graphs with girth at least five under degree constraints
- On a generalization of Nemhauser and Trotter's local optimization theorem
- Parameterized complexity of finding small degree-constrained subgraphs
- Efficient algorithms for decomposing graphs under degree constraints
- Recognizing decomposable graphs
- Algorithms and Computation
- Degree-constrained decompositions of graphs: Bounded treewidth and planarity
Cited In (6)
- An efficient polynomial time approximation scheme for the vertex cover \(P_3\) problem on planar graphs
- The \((3, 3)\)-colorability of planar graphs without 4-cycles and 5-cycles
- Vertex partitioning problems on graphs with bounded tree width
- Title not available (Why is that?)
- Degree-constrained 2-partitions of graphs
- On the kernelization of split graph problems
This page was built for publication: Complexity and kernels for bipartition into degree-bounded induced graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q730002)
