Degree-constrained decompositions of graphs: Bounded treewidth and planarity |
| |
Authors: | Cristina Bazgan Zsolt Tuza Daniel Vanderpooten |
| |
Affiliation: | 1. LAMSADE, Université Paris-Dauphine, Place du Marechal de Lattre de Tassigny, 75775 Paris Cedex 16, France;2. Computer and Automation Institute, Hungarian Academy of Sciences, H-1111 Budapest, Kende u. 13-17, Hungary;3. Department of Computer Science, University of Veszprém, Hungary |
| |
Abstract: | 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 v∈V1 has degree at least a(v) inside V1 and each v∈V2 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. |
| |
Keywords: | Graph decomposition Treewidth Planar graph Polynomial algorithm PTAS |
本文献已被 ScienceDirect 等数据库收录! |
|