Approximation Algorithms for Independent Sets in Map Graphs

✍ Scribed by Zhi-Zhong Chen

• Publisher: Elsevier Science
• Year: 2001
• Tongue: English
• Weight: 172 KB
• Volume: 41
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.2001.1178

✦ Synopsis

This paper presents polynomial-time approximation algorithms for the problem of computing a maximum independent set in a given map graph G with or without weights on its vertices. If G is given together with a map, then a ratio of 1 + δ can be achieved by a quadratic-time algorithm for any given constant δ > 0, no matter whether each vertex of G is given a weight or not. In case G is given without a map, a ratio of 4 can be achieved by a low-degree polynomial-time algorithm if no vertex is given a weight, while a ratio of 5 can be achieved by a low-degree polynomial-time algorithm otherwise.