并行识别无序深度优先搜索树算法
25 浏览量
更新于2024-08-25
收藏 1.01MB PDF 举报
"这篇论文‘Recognizing Unordered Depth-First Search Trees of an Undirected Graph in Parallel (2000)’由Chen-Hsing Peng、Biing-Feng Wang和Jia-Shung Wang撰写，主要探讨了在并行计算环境中识别无序深度优先搜索树（DFS树）的方法。该文提出了一种针对无向图的高效并行算法，用于确定给定的树T是否是图G的DFS树。该算法在EREW PRAM模型上运行，时间复杂度为O(m=p*logm)，其中m表示图G中的边的数量。该算法具有成本最优性和线性速度提升特性。"
这篇论文的焦点在于深度优先搜索（DFS）树在并行计算中的应用。DFS是一种经典图遍历技术，通常用于设计顺序算法。然而，Reif在先前的工作中证明了在并行环境下高效地检查顶点的顺序是否等同于执行有序DFS时得到的访问序列是非常困难的。这引发了关于如何并行化DFS技术的挑战。
论文介绍了一种新的并行算法，旨在解决这个问题。该算法能确定一个给定的树结构T是否是由无向图G通过DFS生成的。在EREW PRAM（Exclusive Read Exclusive Write Parallel Random Access Machine，独占读写并行随机访问机）模型上，这个算法能在p个处理器上运行，并且具有良好的时间复杂度，即O(m=p*logm)，其中m代表图的边数。这意味着随着处理器数量的增加，算法的执行时间将以线性速度减少，这在并行计算中是理想的性能表现。
此外，作者们还提到了索引术语，包括DFS树、生成树、并行算法、PRAM以及欧拉游览技术。欧拉游览技术通常用于处理树和图的问题，它涉及到遍历图的每一条边恰好一次，这在检测DFS树时可能是一个关键工具。
在论文的后续部分，作者可能详细阐述了算法的设计、工作原理、效率分析以及与现有方法的比较。他们可能还讨论了算法的局限性、可能的优化方向以及实际应用案例，展示了如何利用该并行算法在大规模图数据处理中提升性能。
这篇论文为并行计算环境中的图处理提供了一个新的视角，尤其是在无序DFS树的识别方面。它不仅贡献了一种高效算法，还促进了对DFS技术并行化的深入理解，对于并行计算和图算法领域的研究者来说具有重要价值。
in Fig. 1, the nontree edge (v
2
;v
5
) is a cross edge with
respect to T
v
1
, but a back edge with respect to T
v
2
.
For each nontree edge e 2 E ÿ T , we define CROSSe
as the set of vertices v in V such that e is a cross edge with
respect to T
v
. Similarly, for each nontree edge e 2 E ÿ T ,
we define BACKe as the set of vertices v in V such that e
is a back edge with respect to T
v
. Note that for each
nontree edge e 2 E ÿ T , CROSSe\BACKe; and
CROSSe[BACKeV .
We have the following theorem.
Theorem 1. T is an unordered DFT tree of G if and only if
V ÿ
S
e2EÿT
CROSSe is not an empty set.
Proof. Suppose V ÿ
S
e2EÿT
CROSSe is not empty. Let s
be a vertex in V ÿ
S
e2EÿT
CROSSe. For each nontree
edge e 2 E ÿ T , s is not in CROSSe. Therefore, by
definition, all nontree edges in E ÿ T are back edges
with respect to T
s
. Consequently, T
s
is a DFS tree, and
thus, T is a DFS tree of G. The if-part of this theorem is
established.
Now, suppose that T is a DFS tree of G. Recall that T
is a DFS tree of G if and only if there is a vertex v 2 V
such that T
v
has no cross edge. Let s be a vertex in V
such that T
s
has no cross edge. Since T
s
has no cross
edge, s is not in CROSSe for every nontree edge
e 2 E ÿ T . Thus, s is in V ÿ
S
e2EÿT
CROSSe Therefore,
V ÿ
S
e2EÿT
CROSSe is not empty. The only-if part of
this theorem is established. tu
Theorem 1 is a necessary and sufficient condition for
recognizing DFS trees. According to it, our recognition
problem becomes the problem of determining whether V ÿ
S
e2EÿT
CROSSe is empty. In case V ÿ
S
e2EÿT
CROSSe
is not empty, T is a DFS tree of G and each vertex v in
V ÿ
S
e2EÿT
CROSSe is a candidate root of T .
The above discussion provides the base of our recogni-
tion algorithms. Later, in this section, we will give some
properties which are helpful for determining CROSSe for
a given nontree edge e. To speedup the computation of
V ÿ
S
e2EÿT
CROSSe, we need an efficient way to
represent the set V such that we can remove each set
CROSSe easily. In our algorithms, we will use an Euler
tour of T to represent the set V . Using this representation, as
we will show in Section 3, each CROSSe can be removed
from V by performing a constant number of weight
assignments together with a prefix sum computation.
Furthermore, the removal of
S
e2EÿT
CROSSe can be
done efficiently by performing On weight assignments
and a prefix sum computation. Section 3 will define Euler
tours and give a sequential implementation of the above
idea in detail. Most steps of the sequential algorithm
proposed in Section 3 are easily parallelized. However, a
straightforward parallel implementation will result in write
conflicts. Section 4 will provide some noble tricks to avoid
write conflicts and describe our parallel implementation.
First, in the remainder of this section, we give some
properties which are helpful for determining CROSSe
and BACKe for any nontree edge e.
Lemma 1. Let e v; w be a nontree edge in E ÿ T
and treepathv; wv; u
1
; ...;u
k
;w;k>0.Then,
CROSSeV ÿS
v
[ S
w
and BACKeS
v
[ S
w
,
where S
v
and S
w
denote, respectively, the subtree of T
attached to u
1
via the edge v; u
1
and the subtree of T attached
to u
k
via the edge w; u
k
.
Proof. Removing all edges in treepathv; w from T;
k 2 disjoint subtrees can be obtained. Denote
S
v
;S
1
;S
2
; ...;S
k
; and S
w
as the obtained subtrees
containing v; u
1
;u
2
; ...;u
k
, and w, respectively, as shown
in Fig. 2. Consider any vertex x in S
i
; 1 i k.Ifx is
the root of T , the edge v; w is a cross edge. Thus, all
vertices in S
i
; 1 i k, are in CROSSe. On the other
hand, consider any vertex x in S
v
and S
w
.Ifx is the
root of T,theedge(v; w) is a back edge. Thus,
CROSSe
S
1ik
S
i
and BACKeS
v
[ S
w
. Since
S
1ik
S
i
V ÿS
v
[ S
w
, the lemma holds. tu
In the algorithms we shall propose in the next two
sections, we will choose an arbitrary vertex r 2 V and then
orient T into a rooted tree T
r
. In the rooted tree T
r
,a
nontree edge e v; w is either a cross edge or a back edge,
as shown in Fig. 3a and 3b, respectively. Suppose e is a cross
edge in T
r
, as shown in Fig. 3a. In this case, treepathv; w
is the conjunction of the tree path from v up to lcav; w and
the tree path from w up to lcav; w, where lcav; w denotes
the lowest common ancestor of v and w. By comparing
Fig. 3a with Fig. 2, we obtain the following corollary from
Lemma 1 immediately .
Corollary 1. Let e v; w be a cross edge with respect to T
r
.
Then, CROSSeV ÿX
v
[ X
w
and
BACKeX
v
[ X
w
;
where X
v
and X
w
denote the two subtrees in T
r
rooted at v
and w, respectively.
On the other hand, suppose e is a back edge in T
r
,as
shown in Fig. 3b. Without loss of generality, assume v is an
ancestor of w. In this case, treepathv; w can be traced by
starting from w up to v directly. We define childv; w as the
child of v on treepathv; w. By comparing Fig. 3b with
Fig. 2, we obtain the following corollary from Lemma 1
immediately.
PENG ET AL.: RECOGNIZING UNORDERED DEPTH-FIRST SEARCH TREES OF AN UNDIRECTED GRAPH IN PARALLEL 561
Fig. 2. The subtrees S
v
;S
1
;S
2
; ...;S
k
, and S
w
for a nontree edge
e v; w. Subtrees containing vertices in CROSSe are shadowed.
剩余11页未读，继续阅读
2019-01-09 上传
2021-10-25 上传
2021-03-29 上传
2021-08-21 上传
2021-04-16 上传
2021-02-25 上传
2009-08-19 上传
2018-10-12 上传
2019-03-12 上传
weixin_38670186
- 粉丝: 8
- 资源: 945
我的内容管理
展开
最新资源
- SSM Java项目：StudentInfo 数据管理与可视化分析
- pyedgar：Python库简化EDGAR数据交互与文档下载
- Node.js环境下wfdb文件解码与实时数据处理
- phpcms v2.2企业级网站管理系统发布
- 美团饿了么优惠券推广工具-uniapp源码
- 基于红外传感器的会议室实时占用率测量系统
- DenseNet-201预训练模型：图像分类的深度学习工具箱
- Java实现和弦移调工具：Transposer-java
- phpMyFAQ 2.5.1 Beta多国语言版：技术项目源码共享平台
- Python自动化源码实现便捷自动下单功能
- Android天气预报应用：查看多城市详细天气信息
- PHPTML类：简化HTML页面创建的PHP开源工具
- Biovec在蛋白质分析中的应用：预测、结构和可视化
- EfficientNet-b0深度学习工具箱模型在MATLAB中的应用
- 2024年河北省技能大赛数字化设计开发样题解析
- 笔记本USB加湿器：便携式设计解决方案
