Title :
Recognizing unordered depth-first search trees of an undirected graph in parallel
Author :
Peng, Chen-Hsing ; Wang, Biing-Feng ; Wang, Jia-Shung
Author_Institution :
Comput. Center, TaiChung Veteran Gen. Hosp., Taiwan
fDate :
6/1/2000 12:00:00 AM
Abstract :
Let G be an undirected graph and T be a spanning tree of G. In this paper, an efficient parallel algorithm is proposed for determining whether T is an unordered depth-first search tree of G. The proposed algorithm runs in O(m/p+log m) time using p processors on the EREW PRAM, where m is the number of edges contained in G. It is cost-optimal and achieves linear speedup
Keywords :
concurrency theory; graph theory; parallel algorithms; EREW PRAM; depth-first search trees; parallel algorithm; undirected graph; unordered depth-first search tree; Algorithm design and analysis; Parallel algorithms; Phase change random access memory; Processor scheduling; Tree graphs;
Journal_Title :
Parallel and Distributed Systems, IEEE Transactions on
