A deterministic parallel algorithm for determining whether two planar graphs are isomorphic is presented. The algorithm needs O(log n) separators that have to be computed one after the other. The running time is T=O(log/sup 3/ n) time for finding separators, and the processors count is n/sup 1.5/ log n/T. It is also shown that every planar graph has a separator, and a parallel algorithm for finding the separator is given.>

A parallel randomized algorithm for finding the connected components of an undirected graph is presented. The algorithm has an expected running time of $T = O(\log (n))$ with $P = O((m + n) / \log (n))$ processors, where m is the number of edges and n is the number of vertices. The algorithm is optimal in the sense that the product $P \cdot T$ is a linear function of the input size. The algorithm requires $O(m + n)$ space, which is the input size, so it is optimal in space as well.

Article A randomized parallel algorithm for planar graph isomorphism Share on Authors: H. Gazit Department of Computer Science, Duke University, Durham, NC Department of Computer Science, Duke University, Durham, NCView Profile , J. Reif Department of Computer Science, Duke University, Durham, NC Department of Computer Science, Duke University, Durham, NCView Profile Authors Info & Claims SPAA '90: Proceedings of the second annual ACM symposium on Parallel algorithms and architecturesMay 1990 Pages 210–219https://doi.org/10.1145/97444.97687Online:01 May 1990Publication History 4citation468DownloadsMetricsTotal Citations4Total Downloads468Last 12 Months5Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

We present a randomized parallel algorithm for finding a simple cycle separator in a planar graph. The size of the separator is O(√n) and it separates the graph so that the largest part contains at most 2/8 · n vertices. Our algorithm takes T = O(log2(n)) time and P = O(n + f1+ε) processors, where n is the number of vertices, f is the number of faces and ε is any positive constant. The algorithm is based on the solution of Lipton and Tarjan [8] for the sequential case which takes O(n) time. Combining our algorithm with the Pan and Reif [12] algorithm, enables us to find a BFS of planar graph in time O(log3(n)) using n1.5/log(n) processors. Using a variation of our algorithm we can construct a simple cycle separator of size O(d · √f) were d is maximum face size.

We present a parallel randomized algorithm for finding the connected components of an undirected graph. Our algorithm takes T = O(log (n)) time and p = O(m+n/(log(n) processors, where m = number of edges and n = number of vertices. This algorithm improves the results of Cole and Vishkin1, which use O(log (n)·log (log (n))· log (log (log (n)))) time. Our algorithm is Optimal in the sense that the product P·T is a linear function of the input size. The algorithm requires O(m + n) space which is the input size, so it is Optimal in space as well.