Degree-constrained decompositions of graphs: Bounded treewidth and planarity

DOI10.1016/J.TCS.2006.01.024MaRDI QIDQ2369007zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

PTASGraph decompositionPlanar graphPolynomial algorithmTreewidth

Mathematics Subject Classification ID

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)

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

Cites work

• scientific article; zbMATH DE number 1688377 (Why is no real title available?)
• scientific article; zbMATH DE number 944226 (Why is no real title available?)
• scientific article; zbMATH DE number 2102753 (Why is no real title available?)
• scientific article; zbMATH DE number 2104729 (Why is no real title available?)
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A partial k-arboretum of graphs with bounded treewidth
• Algorithmic approach to the satisfactory graph partitioning problem
• Algorithms and Computation
• Algorithms for vertex-partitioning problems on graphs with fixed clique-width.
• Approximation algorithms for NP-complete problems on planar graphs
• Complexity of Finding Embeddings in a k-Tree
• Computing and Combinatorics
• Decomposing graphs with girth at least five under degree constraints
• Diameter and treewidth in minor-closed graph families
• Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
• Efficient algorithms for decomposing graphs under degree constraints
• Fast partitioning l-apex graphs with applications to approximating maximum induced-subgraph problems
• NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
• On decomposition of triangle-free graphs under degree constraints
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• Treewidth. Computations and approximations

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
• Efficient algorithms for decomposing graphs under degree constraints
• Parameterized complexity of satisfactory partition problem
• 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)