An Efficient Parallel Recognition Algorithm For Bipartite-Permutation Graphs.
Journal
IEEE Trans. Parallel Distrib. Syst.
Journal Volume
7
Journal Issue
1
Pages
3-10
Date Issued
1996
Author(s)
Yu, Chang-Wu
Abstract
We present a parallel recognition algorithm for bipartite-permutation graphs. The algorithm can be executed in O(log n) time on the CRCW PRAM if O(n/sup 3//log n) processors are used, or O(log/sup 2/ n) time on the CREW PRAM if O(n/sup 3//log/sup 2/n) processors are used. Chen and Yesha (1993) have presented another CRCW PRAM algorithm that takes O(log/sup 2/n) time if O(n/sup 3/) processors are used. Compared with Chen and Yesha's algorithm, our algorithm requires either less time and fewer processors on the same machine model, or fewer processors on a weaker machine model. Our algorithm can also be applied to determine if two bipartite-permutation graphs are isomorphic.
Type
journal article