Optimal EREW parallel algorithms for connectivity, ear decomposition and st-numbering of planar graphs
- 9 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
Parallel EREW deterministic algorithms for finding the connected components, ear decomposition and st-numbering of a planar graph are presented. The algorithms take O(log(n)) time with /sub log(n)///sup n+m/ processors. Previous results have the same complexity, but use the CRCW model. The same algorithms can be used for graphs with low genus. Let g be the genus of the minimal embedding of the graph, n the number of vertices and m the number of edges. The new algorithm takes T=O(log(n)+log/sup 2/(g)) time and using optimal space and P=O(/sub log(n)///sup n+m/) processors.Keywords
This publication has 15 references indexed in Scilit:
- Optimal parallel algorithms on planar graphsPublished by Springer Nature ,2005
- An optimal parallel algorithm for graph planarityPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1989
- On Finding Lowest Common Ancestors: Simplification and ParallelizationSIAM Journal on Computing, 1988
- Parallel ear decomposition search (EDS) and st-numbering in graphsTheoretical Computer Science, 1986
- Approximate and exact parallel scheduling with applications to list, tree and graph problemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1986
- An efficient parallel algorithm for planarityPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1986
- Parallel merge sortPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1986
- Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithmsPublished by Association for Computing Machinery (ACM) ,1986
- A Separator Theorem for Planar GraphsSIAM Journal on Applied Mathematics, 1979
- Parallel algorithms for the transitive closure and the connected component problemsPublished by Association for Computing Machinery (ACM) ,1976