Name
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. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1016/j.tcs.2006.01.024 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
Degree-constrained decomposition,Graph decomposition,nonempty parts V1,Treewidth,treewidth,local degree condition,polynomial-time algorithm,polynomial algorithm,vertex v,bounded treewidth,Planar graph,Polynomial algorithm,ptas.,graph decomposition,polynomial-time approximation scheme,planar graph,PTAS | Journal | 355 |
Issue | ISSN | Citations |
3 | Theoretical Computer Science | 6 |
PageRank | References | Authors |
0.51 | 19 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Cristina Bazgan | 1 | 679 | 62.76 |
| Zsolt Tuza | 2 | 1889 | 262.52 |
| Daniel Vanderpooten | 3 | 1153 | 74.66 |