Degree-constrained decompositions of graphs: bounded treewidth and planarity
Bazgan, Cristina; Tuza, Zsolt; Vanderpooten, Daniel (2006), Degree-constrained decompositions of graphs: bounded treewidth and planarity, Theoretical Computer Science, 355, 3, p. 389-395. http://dx.doi.org/10.1016/j.tcs.2006.01.024
TypeArticle accepté pour publication ou publié
Journal nameTheoretical Computer Science
MetadataShow full item record
Abstract (EN)We study the problem of decomposing the vertex set V of a graph into two nonempty parts V1,V2 which induce subgraphs where each vertex vset membership, variantV1 has degree at least a(v) inside V1 and each vset membership, variantV2 has degree at least b(v) inside V2. We give a polynomial-time algorithm for graphs with bounded treewidth which decides if a graph admits a decomposition, and gives such a decomposition if it exists. This result and its variants are then applied to designing polynomial-time approximation schemes for planar graphs where a decomposition does not necessarily exist but the local degree conditions should be met for as many vertices as possible.
Subjects / KeywordsPolynomial Algorithm; Treewidth; Graph decomposition; Planar graphs; PTAS
Showing items related by title and author.