๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

An algorithm for optimal isomorphism between two random graphs

โœ Scribed by Dong Su Seong; Young Kyu Choi; Ho Sung Kim; Kyu Ho Park

Publisher
Elsevier Science
Year
1994
Tongue
English
Weight
449 KB
Volume
15
Category
Article
ISSN
0167-8655

No coin nor oath required. For personal study only.

๐Ÿ“œ 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

A Randomized Parallel Algorithm for Plan
A Randomized Parallel Algorithm for Planar Graph Isomorphism
โœ Hillel Gazit; John H Reif ๐Ÿ“‚ Article ๐Ÿ“… 1998 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 223 KB

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

An Optimal Shortest Path Parallel Algori
An Optimal Shortest Path Parallel Algorithm for Permutation Graphs
โœ O.H. Ibarra; Q. Zheng ๐Ÿ“‚ Article ๐Ÿ“… 1995 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 512 KB

We present an optimal parallel algorithm for the single-source shortest path problem for permutation graphs. The algorithm runs in \(O(\log n)\) time using \(O(n / \log n)\) processors on an EREW PRAM. As an application, we show that a minimum connected dominating set in a permutation graph can be f