Complexity and kernels for bipartition into degree-bounded induced graphs
DOI10.1016/J.TCS.2016.11.011zbMATH Open1355.68131OpenAlexW2555985695MaRDI QIDQ730002FDOQ730002
Authors: Mingyu Xiao, Hiroshi Nagamochi 
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
Recommendations
- Complexity and kernels for bipartition into degree-bounded induced graphs
- Degree-constrained 2-partitions of graphs
- Parameterized complexity of finding regular induced subgraphs
- The path partition problem and related problems in bipartite graphs
- The parameterized complexity of the induced matching problem
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 (8)
- 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
- Degree-constrained 2-partitions of graphs
- On the kernelization of split graph problems
- Complexity and kernels for bipartition into degree-bounded induced graphs
- Brief announcement: Bounded-degree cut is fixed-parameter tractable
- Partition a graph with small diameter into two induced matchings
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)
