Recognizing Unordered Depth-First Search
Trees of an Undirected Graph in Parallel
Chen-Hsing Peng, Member, IEEE, Biing-Feng Wang, Member, IEEE, and Jia-Shung Wang
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 Om=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.
Index TermsÐDepth-first search trees, spanning trees, parallel algorithms, PRAM, the Euler-tour technique.
æ
1INTRODUCTION
D
EPTH-FIRST search, abbreviated as DFS, is well-known to
be an important technique for designing sequential
algorithms on graphs [13]. One might expect that if the DFS
technique can be parallelized efficiently, a lot of sequential
graph algorithms can be done as well. Unfortunately, Reif
[10] proved that it seems very hard to check efficiently in
parallel whether a given order of vertices is equal to the
visiting sequence obtained by performing an ordered DFS
on a graph, and concluded that ordered DFS is inherently
sequential. By ªorderedº we mean that for each vertex u in
the DFS tree its children are visited in the same order as
they appear on the adjacency list of u. Reif's result is
pessimistic. Therefore, many researchers turned their
attention to other related topics. When the ordered
restriction is removed, some positive results can be derived.
Hagerup [5] proposed an Olog n time parallel unordered
DFS algorithm on planar undirected graphs. Aggarwal et al.
[1] proposed a randomized NC algorithm for performing
unordered DFSs on general directed graphs. Opposite to the
construction of a DFS tree, Schevon and Vitter [11]
considered the problem of determining whether a given
spanning tree of a directed graph is an unordered DFS tree
of the graph. Schevon and Vitter showed that the problem
can be solved in Olog
2
n time.
In this paper, we study the problem of determining
whether a given spanning tree of an undirected graph is an
unordered DFS tree of the graph. We show that for an
undirected graph containing n vertices and m n ÿ 1
edges, its unordered DFS trees can be recognized in
Om=p log m time using p processors on the EREW
PRAM.
The problem of verifying whether a given spanning tree
satisfies some specific properties is of theoretical interest.
Thus, the problem of recognizing various spanning trees
had been extensively studied in literatures. For example,
besides DFS trees, Manber [8] studied the problem of
recognizing breadth-first search trees, Tarjan [14] and
Chazelle [2] studied the problem of recognizing minimum
spanning trees, and Peng et al. [9] studied the problem of
recognizing shortest path trees.
An efficient algorithm for recognizing DFS trees has
several applications [7], [11]. For example, in [11], it was
mentioned that an efficient algorithm for recognizing DFS
trees can be used as a subroutine for an algorithm that
constructs a DFS tree by successively generating candidates
until a valid one is obtained. In [7], Korach and Ostfeld gave
two examples. Consider an undirected graph G in which no
two edges have the same weight. The first example in [7]
was to answer the following question: Is the unique
minimum spanning tree of G obtained by performing a
DFS in G? The second example, described in [7], is to solve a
certain task scheduling problem. The description of the
application is long and thus omitted here.
Besides being of theoretical interest, the recognition
problem of DFS trees is also of practical importance. In the
real world, a computation environment is not always
reliable. Thus, it is necessary to verify the outputs of a
DFS tree construction algorithm or to check the validness of
a DFS tree inputted into a procedure.
Consider that G V;E is an undirected graph com-
posed of jV jn vertices and jEjm n ÿ 1 edges. An
unordered depth-first search tree, or abbreviated as unordered
DFS tree,ofG is a rooted spanning tree of G output by
performing the following nondeterministic DFS algorithm.
Algorithm 1. (Unordered depth-first search)
Input: An undirected connected graph G.
Output: An unordered DFS tree T of G.
a. Select a vertex r as the starting point.
b. call DFS(r).
Procedure DFS(v)
1. Mark v as visited.
2. for each vertex w adjacent to v do
3. if w is not visited then mark (v; w) as an edge of T
and call DFS(w).
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 11, NO. 6, JUNE 2000 559
. C.H. Peng is with the Computer Center, TaiChung Veteran General
Hospital, TaiChung, Taiwan 40717, Republic of China.
. B.-F. Wang and J.-S. Wang are with the Department of Computer Science,
National Tsing Hua University, Hsinchu, Taiwan 30043, Republic of
China. E-mail: bfwang@cs.nthu.edu.tw.
Manuscript received 27 June 1997; revised 26 June 1998; accepted 19 Jan.
2000.
For information on obtaining reprints of this article, please send e-mail to:
tpds@computer.org, and reference IEEECS Log Number 105298.
1045-9219/00/$10.00 ß 2000 IEEE
剩余11页未读，继续阅读
资源评论
