DocumentCode
2633896
Title
Recognizing depth-first-search trees in parallel
Author
Wang, J.S. ; Wang, B.F. ; Peng, C.H.
Author_Institution
Dept. of Comput. Sci., Nat. Tsing Hua Univ., Hsinchu, Taiwan
fYear
1995
fDate
25-28 Apr 1995
Firstpage
101
Lastpage
105
Abstract
Consider that T. is a given spanning tree of an undirected graph G which contains a vertices and m (⩾n-1) edges. In this paper, we propose an O(m/p+log m)-time parallel algorithm using p processors on the EREW PRAM model to determine whether T is a depth-first-search tree of G. Our algorithm is optimal in time complexity and speed-up
Keywords
computational complexity; directed graphs; parallel algorithms; search problems; tree searching; EREW PRAM model; depth-first-search trees; parallel algorithm; spanning tree; speed-up; time complexity; undirected graph; Classification tree analysis; Hospitals; IEL; Joining processes; Phase change random access memory; Sufficient conditions; Tree graphs;
fLanguage
English
Publisher
ieee
Conference_Titel
Parallel Processing Symposium, 1995. Proceedings., 9th International
Conference_Location
Santa Barbara, CA
Print_ISBN
0-8186-7074-6
Type
conf
DOI
10.1109/IPPS.1995.395920
Filename
395920
Link To Document