Efficient Approximation Schemes for Maximization Problems onK3, 3-free orK5-free Graphs
✍ Scribed by Zhi-Zhong Chen
- Publisher
- Elsevier Science
- Year
- 1998
- Tongue
- English
- Weight
- 263 KB
- Volume
- 26
- Category
- Article
- ISSN
- 0196-6774
No coin nor oath required. For personal study only.
✦ Synopsis
We show that for any integer k G 2 and any n-vertex graph G without a K 3, 3 Ž . or K minor, one can compute k induced subgraphs of G with treewidth no more 5 Ž . Ž. Ž Ž 2 .. than 3k y 4 respectively, 6 k y 7 in O kn respectively, O kn q n time such that each vertex of G appears in exactly k y 1 of these subgraphs. This leads to practical polynomial-time approximation schemes for various maximum induced-Ž . subgraph problems on graphs without a K respectively, K minor. The result 3, 3 5 extends the well-known practical polynomial-time approximation schemes of Baker for various maximum induced-subgraph problems on planar graphs. ᮊ 1998 Aca- demic Press
* A preliminary version of this paper appeared as Practical approximation schemes for maximum induced-subgraph problems on K -free or K -free graphs, in ''Proceedings of the 3, 3 5