An efficient parallel algorithm for computing a large independent set in a planar graph
- 1 June 1991
- journal article
- Published by Springer Nature in Algorithmica
- Vol. 6 (1-6) , 801-815
- https://doi.org/10.1007/bf01759072
Abstract
No abstract availableKeywords
This publication has 15 references indexed in Scilit:
- Some simplified NP-complete graph problemsPublished by Elsevier ,2002
- Optimal Parallel 5-Colouring of Planar GraphsSIAM Journal on Computing, 1989
- Parallel Symmetry-Breaking in Sparse GraphsSIAM Journal on Discrete Mathematics, 1988
- On linear-time algorithms for five-coloring planar graphsInformation Processing Letters, 1984
- Approximation algorithms for NP-complete problems on planar graphsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1983
- An Approximation Algorithm for the Maximum Independent Set Problem on Planar GraphsSIAM Journal on Computing, 1982
- A linear 5-coloring algorithm of planar graphsJournal of Algorithms, 1981
- Every planar map is four colorableBulletin of the American Mathematical Society, 1976
- Efficient Planarity TestingJournal of the ACM, 1974
- A Theorem on Coloring the Lines of a NetworkJournal of Mathematics and Physics, 1949