✦ LIBER ✦

A Randomized Parallel Algorithm for Planar Graph Isomorphism

✍ Scribed by Hillel Gazit; John H Reif

Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 223 KB
Volume: 28
Category: Article
ISSN: 0196-6774
DOI: 10.1006/jagm.1998.0943

No coin nor oath required. For personal study only.

✦ Synopsis

We present a parallel randomized algorithm running on a CRCW PRAM, to determine whether two planar graphs are isomorphic, and if so to find the isomorphism. We assume that we have a tree of separators for each planar graph Ž Ž 2 .

1 q ⑀ which can be computed by known algorithms in O log n time with n . processors, for any ⑀ ) 0 . If n is the number of vertices, our algorithm takes

O log n time with P s O n и log n processors and with a probability of Ž .

Ž . Ž . Ž Ž .. failure of 1rn at most. The algorithm needs 2 и log m y log n q O log n ran-Ž Ž .. dom bits. The number of random bits can be decreased to O log n by increasing the number of processors to n 3r 2q⑀ , for any ⑀ ) 0. Our parallel algorithm has significantly improved processor efficiency, compared to the previous logarithmic Ž Ž . . time parallel algorithm of Miller and Reif Siam J. Comput. 20 1991 , 1128᎐1147 , which requires n 4 randomized processors or n 5 deterministic processors.

📜 SIMILAR VOLUMES

An Optimal Simple Parallel Algorithm for

An Optimal Simple Parallel Algorithm for Testing Isomorphism of Maximal Outerplanar Graphs

✍ Shan-Chyun Ku; Biing-Feng Wang 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 91 KB

An outerplanar graph is a planar graph that can be imbedded in the plane in such a way that all vertices lie on the exterior face. An outerplanar graph is maximal if no edge can be added to the graph without violating the outerplanarity. In this paper, an optimal parallel algorithm is proposed on th

An algorithm for drawing planar graphs

✍ Bor Plestenjak 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 382 KB 👁 2 views

A simple algorithm for drawing 3-connected planar graphs is presented. It is derived from the Fruchterman and Reingold spring embedding algorithm by deleting all repulsive forces and fixing vertices of an outer face. The algorithm is implemented in the system for manipulating discrete mathematical s

Parallel Algorithms for Reducible Flow G

Parallel Algorithms for Reducible Flow Graphs

✍ Vijaya Ramachandran 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 324 KB

We present parallel NC algorithms for recognizing a reducible flow graph rfg and for finding dominators, minimum feedback vertex sets, and a depth first search Ž . tree in an rfg. On an n-node rfg, all of these algorithms run in polylog n time Ž . Ž . using M n processors, where M n is the number o

A SimpleO(log N) Time Parallel Algo

A SimpleO(log N) Time Parallel Algorithm for Testing Isomorphism of Maximal Outerplanar Graphs

✍ Srabani Sen Gupta; Bhabani P. Sinha 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 195 KB

Algorithms for coloring semi-random grap

Algorithms for coloring semi-random graphs

✍ C. R. Subramanian; Martin Fürer; C. E. Veni Madhavan 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 373 KB 👁 3 views

The graph coloring problem is to color a given graph with the minimum number of colors. This problem is known to be NP-hard even if we are only aiming at approximate solutions. On the other hand, the best known approximation algorithms require ␦ Ž . Ž . n ␦ ) 0 colors even for bounded chromatic k-co

Faster Shortest-Path Algorithms for Plan

Faster Shortest-Path Algorithms for Planar Graphs

✍ Monika R Henzinger; Philip Klein; Satish Rao; Sairam Subramanian 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 445 KB

We give a linear-time algorithm for single-source shortest paths in planar graphs with nonnegative edge-lengths. Our algorithm also yields a linear-time algorithm for maximum flow in a planar graph with the source and sink on the same face. For the case where negative edge-lengths are allowed, we gi