RecognizingUnorderedDepth-FirstSearchTreesofanUndirectedGraphinParallel(2000)-计算机科学资源-CSDN文库

73 浏览量 2021-04-22 18:04:49 上传评论收藏 1.01MB PDF 举报

资源推荐

资源详情

资源评论

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 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.

Index TermsÐDepth-first search trees, spanning trees, parallel algorithms, PRAM, the Euler-tour technique.

1INTRODUCTION

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 Olog 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 Olog

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

Om=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 jn vertices and jEjm 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

The starting point selected in Step a is treated as the root

of the output DFS tree. Since Steps a and 2 are nondetermi-

nistic, there may be more than one unordered DFS tree. To

recognize an unordered DFS tree is to determine whether a

given spanning tree is a possible output of the above

unordered depth first search algorithm, and to decide the

visiting order. In fact, if T is known to be an unordered DFS

tree of graph G, the visiting order can be derived by

performing a preorder traversal on T using the algorithm

proposed by Chen, Das, and Akl in [3].

The nondeterminism of Steps a and 2 makes the

recognition problem more complicated. Suppose that these

two steps are deterministic, i.e., a specific vertex r is

designated as the root of T , and for each vertex v we

traverse the adjacent vertices of v following the order of the

prescribed adjacency list of it. Then, to check whether T is a

DFS tree or not can be simply done in linear time using the

common depth first search algorithm. Note that in case the

two steps are deterministic, the obtained DFS tree is

ordered. If only step 2 is nondeterministic and a specific

vertex r is designated as the root of T , we can verify easily

by using the famous property of DFS trees: T is a DFS tree if

and only if T has no cross edge [11]. In the case that both

Steps a and 2 are nondeterministic, a linear time sequential

algorithm for recognizing unordered DFS trees was

proposed by Korach and Ostfeld [7].

The recognition problem for the case of directed graphs

can be defined similarly. The recognition problem on

directed graphs are harder than that on undirected graphs,

because an undirected graph can be easily converted into a

directed one by replacing each undirected edge (v; w) with

two directed edges (v; w) and (w; v), and then can be solved

by using the algorithms for directed graphs. Schevon and

Vitter [11] showed that the recognition of unordered DFS

trees for directed graphs can be done in Olog

n time using

On

2:376

 processors on a CREW PRAM. In the directed case,

there is only one vertex of in-degree 0 in a directed

spanning tree T , and thus the root is always designated. In

this paper, we show that the recognition for undirected

graphs without a designated root can be done in Om=p 

log m parallel time using p processors on the EREW PRAM.

The major technique utilized in our algorithms is the Euler-

tour technique [12], [15], [16], which is well-known to be a

good paradigm for designing efficient parallel algorithms

on trees.

The remainder of this paper is organized as follows: In

Section 2, a necessary and sufficient condition for recogniz-

ing unordered DFS trees is given. In Section 3, we present a

linear time sequential recognition algorithm. In Section 4, by

parallelizing the sequential algorithm proposed in Section 3,

an efficient parallel solution is presented on the EREW

PRAM. Finally, in Section 5, we conclude this paper.

2ANECESSARY AND SUFFICIENT CONDITION FOR

RECOGNIZING DFS TREES

Let G V;E be an undirected graph composed of

jV jn vertices and jEjm edges, and T be a spanning

tree of G. The edges of T are called tree edges, and the edges

of E ÿ T are called nontree edges.Atree path is a simple path

going along only tree edges. Since the tree path connecting

any two vertices v and w is unique, it can be unambiguously

denoted as treepathv; w. Note that the given spanning tree

T is a free tree, that is, no root is designated. When a root r

is assigned for T, the spanning tree will be denoted as T

r

instead.

If a rooted spanning tree T

r

is given, the recognition

problem will become simple. In such a case, all nontree

edges can be classified into two classes: cross edges and

back edges. A nontree edge (v; w) is called a cross edge if v

and w are not ancestors of each other; otherwise, it is called

a back edge. It is well-known that T

r

is a DFS tree of G if and

only if there is no cross edge, or equivalently, all nontree

edges are back edges [11]. For example, consider the tree T

and the graph G depicted in Fig. 1. If we select v

as the

root, T

v



is not a DFS tree, since it has two cross edges:

) and (v

). On the other hand, if we select v

as the

root, T

v



is a DFS tree, since it has no cross edge. Thus, to

recognize a DFS tree T

r

can be done with the following

procedure.

1. Use Chen, Das, and Akl's algorithm in [3] to

determine the preorder number prev and the

postorder number postv for every vertex v 2 T

r

in On=p  log n time using p processors on the

EREW PRAM.

2. Check whether all nontree edges are back edges.

Given two vertices v and w in T

r

, to check whether v

is an ancestor of w is equivalent to verifying whether

prev < prew and postv > postw [6], which can

be done in O1 time using a single processor. Thus,

this step can be easily implemented in Om=p 

log m time using p processors on the EREW PRAM.

The total time complexity of the above procedure is

Om=p  log m.

In our problem, the root of the given spanning tree T is

not designated. Since any vertex v of T could be the root

such that T

v

is a DFS tree, it is necessary to check for every

vertex v whether all nontree edges are back edges with

respect to T

v

. Such a vertex v is called a candidate root of T .

The tree T is a DFS tree if and only if there exists a

candidate root. Thus, the main job of our recognition

problem is to determine if there exists a candidate root.

We should be aware of that the terms ªcross edgeª and

ªback edgeª are meaningful only for a rooted tree. A

nontree edge may be a cross edge with respect to some root,

but a back edge with respect to another root. For example,

560 IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 11, NO. 6, JUNE 2000

Fig. 1. A spanning tree T of a graph G (bold/fine edges: tree/nontree

edges).

剩余11页未读，继续阅读

评论收藏

内容反馈

weixin_38670186

粉丝: 8
资源: 945

Recognizing Unordered Depth-First Search Trees of an Undirected ...

最新资源

Recognizing Unordered Depth-First Search Trees of an Undirected ...

Depth-First-Search

Undirected Graphs

Graph-Based Semi-Supervised Learning

06-recognizing-and-beating-cyber-fatigue.zip

Knowledge-Embedded Routing Network for Scene Graph Generation.pdf

tv-r06-recognizing-and-beating-cyber-fatigue.pdf

Graph-theoretic algorithms

An End-to-End Network for Generating Social Relationship Graphs.pdf

Detecting and Recognizing Human-Object Interactions

Multi-digit Number Recognition from Street View Imagery using DCNN

Recognizing-the-place-of-birth-from-the-image-of-the-person-s-face:通过HOG和LBP描述符对人脸进行分类； 使用支持向量机，逻辑回归和随机森林分类器

Beyond Bags of Features: Spatial Pyramid Matching for Recognizing Natural Scene Categories

recognizing-the-human-eyes:使用Python的程序可以检测人眼

Paul Ekman - Unmasking The Face. A guide to recognizing emotions from facial clues.part1.rar

Paul Ekman - Unmasking The Face. A guide to recognizing emotions from facial clues.part2.rar

Detecing and Recognizing Human-Object Interactions

英文原版-Learning Radiology Recognizing the Basics 3rd Edition

Java in easy steps: Covers Java 9, 6th Edition - epub格式

Handbook of Research on Soft Computing and Nature-Inspired Algorithms

Mastering Machine Learning with R - Second Edition

具有多重抓取和跨域图像匹配的杂波中的新物体的机器人拾取和放置

Voltage-Sourced Converters in Power Systems

Albert-László Barabási的2018年新书《The Formula：the universal laws of success》

英文原版-Rotator Cuff Deficiency of the Shoulder 1st Edition

最新资源

Recognizing-the-place-of-birth-from-the-image-of-the-person-s-face:通过HOG和LBP描述符对人脸进行分类；使用支持向量机，逻辑回归和随机森林分类器