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