Splitting a graph into disjoint induced paths or cycles.
From MaRDI portal
Publication:1408827
DOI10.1016/S0166-218X(02)00425-0zbMath1073.68031MaRDI QIDQ1408827
Haiko Müller, Hoàng-Oanh Le, Van Bang Le
Publication date: 25 September 2003
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Planar graphs; geometric and topological aspects of graph theory (05C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (11)
Finding good 2-partitions of digraphs. I. Hereditary properties ⋮ Finding good 2-partitions of digraphs. II. Enumerable properties ⋮ Extremal values and bounds for the zero forcing number ⋮ Grid representations and the chromatic number ⋮ Induced-path partition on graphs with special blocks ⋮ Reprint of: ``Grid representations and the chromatic number ⋮ Fast-mixed searching and related problems on graphs ⋮ Degree-constrained 2-partitions of graphs ⋮ Induced path factors of regular graphs ⋮ Parameterizing path partitions ⋮ The parameterized complexity landscape of finding 2-partitions of digraphs
Cites Work
- Unnamed Item
- Unnamed Item
- Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
- The complexity of some problems related to GRAPH 3-COLORABILITY
- Treewidth. Computations and approximations
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Easy problems for tree-decomposable graphs
- Graph minors. II. Algorithmic aspects of tree-width
- Complexity of Finding Embeddings in a k-Tree
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
This page was built for publication: Splitting a graph into disjoint induced paths or cycles.
