Degree-constrained decompositions of graphs: Bounded treewidth and planarity
From MaRDI portal
Publication:2369007
DOI10.1016/j.tcs.2006.01.024zbMath1088.68138OpenAlexW2033951727MaRDI QIDQ2369007
Zsolt Tuza, Cristina Bazgan, Daniel Vanderpooten
Publication date: 28 April 2006
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2006.01.024
Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (10)
The balanced satisfactory partition problem ⋮ Structural and algorithmic properties of 2-community structures ⋮ New Insight into 2-Community Structures in Graphs with Applications in Social Networks ⋮ Vertex partitioning problems on graphs with bounded tree width ⋮ Complexity and Kernels for Bipartition into Degree-bounded Induced Graphs ⋮ Degree-constrained 2-partitions of graphs ⋮ Unnamed Item ⋮ Satisfactory graph partition, variants, and generalizations ⋮ Complexity and kernels for bipartition into degree-bounded induced graphs ⋮ Parameterized complexity of satisfactory partition problem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fast partitioning \(l\)-apex graphs with applications to approximating maximum induced-subgraph problems
- Efficient algorithms for decomposing graphs under degree constraints
- Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
- A partial k-arboretum of graphs with bounded treewidth
- Treewidth. Computations and approximations
- Diameter and treewidth in minor-closed graph families
- Algorithmic approach to the satisfactory graph partitioning problem
- Algorithms for vertex-partitioning problems on graphs with fixed clique-width.
- Complexity of Finding Embeddings in a k-Tree
- The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
- Approximation algorithms for NP-complete problems on planar graphs
- On decomposition of triangle-free graphs under degree constraints
- NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
- Decomposing graphs with girth at least five under degree constraints
- Algorithms and Computation
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Computing and Combinatorics
This page was built for publication: Degree-constrained decompositions of graphs: Bounded treewidth and planarity
