NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs

✍ Scribed by Harry B Hunt III; Madhav V Marathe; Venkatesh Radhakrishnan; S.S Ravi; Daniel J Rosenkrantz; Richard E Stearns

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 303 KB
• Volume: 26
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.1997.0903

✦ Synopsis

We present NC-approximation schemes for a number of graph problems when restricted to geometric graphs including unit disk graphs and graphs drawn in a civilized manner. Our approximation schemes exhibit the same time versus performance trade-off as the best known approximation schemes for planar graphs. We also define the concept of -precision unit disk graphs and show that for such * A preliminary version of this paper appeared in ''Proc. 2nd European Symposium on Ž .Ž . Algorithms ESA'94 pp. 424᎐435, Springer-Verlag, BerlinrNew York .