Degree-constrained decompositions of graphs: Bounded treewidth and planarity

详细信息	查看全文 | 推荐本文 |

• 作者：Cristina Bazgan ; Zsolt Tuza and Daniel Vanderpooten
• 关键词：Graph decomposition ; Treewidth ; Planar graph ; Polynomial algorithm ; PTAS
• 刊名：Theoretical Computer Science
• 出版年：2006
• 期刊代码：114_03043975
• 类别：cp
• 出版时间：14 April 2006
• 卷：355
• 期：3
• 页码：389-395
• 文件大小：194 K

摘要

We study the problem of decomposing the vertex set V of a graph into two nonempty parts V₁,V₂ which induce subgraphs where each vertex 140d13418e9771" title="Click to view the MathML source">vV₁ has degree at least 3440036270" title="Click to view the MathML source">a(v) inside V₁ and each vV₂ has degree at least b(v) inside V₂. 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.