NC-approximation schemes for NP- and PSPACE-hard problems for geometric graphs. (English) Zbl 0894.68105

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

J. Algorithms 26, No. 2, 238-274 (1998).

Summary: 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 \(\lambda\)-precision unit disk graphs and show that for such graphs the approximation schemes have a better time versus performance trade-off than the approximation schemes for arbitrary unit disk graphs. Moreover, compared to unit disk graphs, we show that for \(\lambda\)-precision unit disk graphs many more graph problems have efficient approximation schemes.
Our NC-approximation schemes can also be extended to obtain efficient NC-approximation schemes for several PSPACE-hard problems on unit disk graphs specified using a restricted version of the hierarchical specification language of Bentley, Ottmann, and Widmayer. The approximation schemes for hierarchically specified unit disk graphs presented in this paper are among the first approximation schemes in the literature for natural PSPACE-hard optimization problems.

MSC:

68R10

Graph theory (including graph drawing) in computer science

Keywords:

NC-approximation schemes; PSPACE-hard optimization problems