Optimal parallel algorithm for graph planarity
Publication
, Journal Article
Ramachandran, V; Reif, J
Published in: Annual Symposium on Foundations of Computer Science (Proceedings)
January 1, 1989
The authors present a parallel algorithm based on open ear decomposition which, given a graph G on n vertices, constructs an embedding of G onto the plane or reports that G is nonplanar. This parallel algorithm runs on a concurrent-read, concurrent-write parallel random-access machine (CRCW PRAM) in O(log n) time with the same processor bound as graph connectivity.
Duke Scholars
Published In
Annual Symposium on Foundations of Computer Science (Proceedings)
DOI
ISSN
0272-5428
Publication Date
January 1, 1989
Start / End Page
282 / 287
Citation
APA
Chicago
ICMJE
MLA
NLM
Ramachandran, V., & Reif, J. (1989). Optimal parallel algorithm for graph planarity. Annual Symposium on Foundations of Computer Science (Proceedings), 282–287. https://doi.org/10.1109/sfcs.1989.63491
Ramachandran, V., and J. Reif. “Optimal parallel algorithm for graph planarity.” Annual Symposium on Foundations of Computer Science (Proceedings), January 1, 1989, 282–87. https://doi.org/10.1109/sfcs.1989.63491.
Ramachandran V, Reif J. Optimal parallel algorithm for graph planarity. Annual Symposium on Foundations of Computer Science (Proceedings). 1989 Jan 1;282–7.
Ramachandran, V., and J. Reif. “Optimal parallel algorithm for graph planarity.” Annual Symposium on Foundations of Computer Science (Proceedings), Jan. 1989, pp. 282–87. Scopus, doi:10.1109/sfcs.1989.63491.
Ramachandran V, Reif J. Optimal parallel algorithm for graph planarity. Annual Symposium on Foundations of Computer Science (Proceedings). 1989 Jan 1;282–287.
Published In
Annual Symposium on Foundations of Computer Science (Proceedings)
DOI
ISSN
0272-5428
Publication Date
January 1, 1989
Start / End Page
282 / 287