Degree-constrained decompositions of graphs: Bounded treewidth and planarity
DOI10.1016/J.TCS.2006.01.024zbMATH Open1088.68138OpenAlexW2033951727MaRDI QIDQ2369007FDOQ2369007
Authors: Cristina Bazgan, Zsolt Tuza, 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
Recommendations
- Efficient algorithms for decomposing graphs under degree constraints
- Degree sequence optimization in bounded treewidth
- Approximate tree decompositions of planar graphs in linear time
- Large-treewidth graph decompositions and applications
- Approximate tree decompositions of planar graphs in linear time
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- A partial k-arboretum of graphs with bounded treewidth
- Complexity of Finding Embeddings in a k-Tree
- Approximation algorithms for NP-complete problems on planar graphs
- Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
- Treewidth. Computations and approximations
- Fast partitioning \(l\)-apex graphs with applications to approximating maximum induced-subgraph problems
- Title not available (Why is that?)
- The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
- Diameter and treewidth in minor-closed graph families
- Algorithmic approach to the satisfactory graph partitioning problem
- On decomposition of triangle-free graphs under degree constraints
- Title not available (Why is that?)
- Title not available (Why is that?)
- Decomposing graphs with girth at least five under degree constraints
- NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
- Algorithms for vertex-partitioning problems on graphs with fixed clique-width.
- Title not available (Why is that?)
- Computing and Combinatorics
- Efficient algorithms for decomposing graphs under degree constraints
- Algorithms and Computation
Cited In (17)
- The balanced satisfactory partition problem
- Vertex partitioning problems on graphs with bounded tree width
- New upper bounds on the decomposability of planar graphs
- Constant-degree graph expansions that preserve treewidth
- Structural and algorithmic properties of 2-community structures
- Complexity and kernels for bipartition into degree-bounded induced graphs
- New insight into 2-community structures in graphs with applications in social networks
- Degree-constrained 2-partitions of graphs
- Decomposing planar graphs into graphs with degree restrictions
- Complexity and kernels for bipartition into degree-bounded induced graphs
- Parameterized complexity of satisfactory partition problem
- Efficient algorithms for decomposing graphs under degree constraints
- Satisfactory graph partition, variants, and generalizations
- Degree sequence optimization in bounded treewidth
- Brief announcement: Bounded-degree cut is fixed-parameter tractable
- Trees and Co-trees with Bounded Degrees in Planar 3-connected Graphs
- Constant-Factor Approximations of Branch-Decomposition and Largest Grid Minor of Planar Graphs in O(n 1 + ε ) Time
This page was built for publication: Degree-constrained decompositions of graphs: Bounded treewidth and planarity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2369007)
