Title :
An efficient parallel recognition algorithm for bipartite-permutation graphs
Author :
Yu, Chang-Wu ; Chen, Gen-Huey
Author_Institution :
Dept. of Comput. Sci. & Inf. Eng., Nat. Taiwan Univ., Taipei, Taiwan
fDate :
1/1/1996 12:00:00 AM
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(n3/log n) processors are used, or O(log2 n) time on the CREW PRAM if O(n3/log2 n) processors are used. Chen and Yesha (1993) have presented another CRCW PRAM algorithm that takes O(log2n) time if O(n 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
Keywords :
computational complexity; graph theory; parallel algorithms; CRCW PRAM; CREW PRAM; bipartite-permutation graphs; computation time; efficient parallel recognition algorithm; isomorphic bipartite-permutation graphs; machine model; processors; Bipartite graph; Computer science; Dynamic programming; Genetic mutations; Optimal scheduling; Parallel algorithms; Phase change random access memory; Testing;
Journal_Title :
Parallel and Distributed Systems, IEEE Transactions on
