NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
- 1 February 1998
- journal article
- Published by Elsevier in Journal of Algorithms
- Vol. 26 (2) , 238-274
- https://doi.org/10.1006/jagm.1997.0903
Abstract
No abstract availableThis publication has 29 references indexed in Scilit:
- Hierarchically specified unit disk graphsTheoretical Computer Science, 1997
- Separators for sphere-packings and nearest neighbor graphsJournal of the ACM, 1997
- Simple heuristics for unit disk graphsNetworks, 1995
- Approximation algorithms for NP-complete problems on planar graphsJournal of the ACM, 1994
- The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problemsJournal of Computer and System Sciences, 1992
- Easy problems for tree-decomposable graphsJournal of Algorithms, 1991
- Linear time algorithms for NP-hard problems restricted to partial k-treesDiscrete Applied Mathematics, 1989
- Fast approximation algorithms for a nonconvex covering problemJournal of Algorithms, 1987
- Approximation schemes for covering and packing problems in image processing and VLSIJournal of the ACM, 1985
- Outage Probability in Mobile Telephony with Directive Antennas and MacrodiversityIEEE Journal on Selected Areas in Communications, 1984