✦ LIBER ✦
Fast partitioning l-apex graphs with applications to approximating maximum induced-subgraph problems
✍ Scribed by Dimitrios M. Thilikos; Hans L. Bodlaender
- Publisher
- Elsevier Science
- Year
- 1997
- Tongue
- English
- Weight
- 542 KB
- Volume
- 61
- Category
- Article
- ISSN
- 0020-0190
No coin nor oath required. For personal study only.
✦ Synopsis
A graph is Z-apex if it can be made planar by removing at most 1 vertices. In this paper we show that the vertex set of any graph not containing an l-apex graph as a minor can be partitioned in linear time into 2' sets inducing graphs with small treewidth. As a consequence, several maximum induced-subgraph problems when restricted to graph classes not containing some special l-apex graphs as minors, have practical approximation algorithms. @ 1997 Elsevier Science B.V.