A Unified Approach to Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
Lists
Only you see this
Abstract
We present parallel approximation schemes for a number of graph problems when restricted to geometric graphs including unit disk graphs and graphs drawn in a civilized manner [CCJ90, MHR92, Te91]. Our NC-approximation schemes exhibit the same time versus performance trade-off as those of Baker [Ba83]. We also define the concept of λ-precision unit disk graphs and show that for such graphs our NC approximation schemes have better time versus performance trade-offs and several other graph problems have efficient approximation schemes. Our parallel approximation schemes can also be extended to obtain efficient parallel approximation schemes for problems on unit disk graphs specified using a restricted version of the hierarchical specification language of Bentley, Ottmann and Widmayer [BOW83]. While we can show that many graph problems are PSPACE-hard even for this restricted form of specifications, nevertheless, these problems possess efficient approximation schemes.
BibTeX
@inproceedings{iii1994unified,
author = {Harry B. Hunt III and Madhav V. Marathe and Venkatesh Radhakrishnan and S. S. Ravi and Daniel J. Rosenkrantz and Richard Edwin Stearns},
title = {{A Unified Approach to Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs}},
booktitle = {ESA},
year = {1994},
url = {https://openreview.net/forum?id=AiUCURRUT0C},
}Loading related content...