Approximation algorithms for NP-complete problems on planar graphs
- 2 January 1994
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 41 (1), 153-180
- https://doi.org/10.1145/174644.174650
Abstract
No abstract availableThis publication has 10 references indexed in Scilit:
- Partitioning Planar GraphsSIAM Journal on Computing, 1992
- On the complexity of embedding planar graphs to minimize certain distance measuresAlgorithmica, 1990
- Generalized planar matchingJournal of Algorithms, 1990
- An Approximation Algorithm for the Maximum Independent Set Problem on Planar GraphsSIAM Journal on Computing, 1982
- Linear-time computability of combinatorial problems on series-parallel graphsJournal of the ACM, 1982
- On the Problem of Partitioning Planar GraphsSIAM Journal on Algebraic Discrete Methods, 1982
- Linear algorithms on recursive representations of treesJournal of Computer and System Sciences, 1979
- A linear algorithm for the domination number of a treeInformation Processing Letters, 1975
- Efficient Planarity TestingJournal of the ACM, 1974
- Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal GraphSIAM Journal on Computing, 1972