EFFICIENT PARALLEL GRAPH ALGORITHMS BASED ON OPEN EAR DECOMPOSITION

被引：0
|
作者：
IBARRA, L [1 ]
RICHARDS, D [1 ]
机构：
[1] NATL SCI FDN, DIV COMP & COMPUTAT RES, WASHINGTON, DC 20550 USA
来源：
PARALLEL COMPUTING | 1993年 / 19卷 / 08期
基金：
美国国家航空航天局;
关键词：
PARALLEL GRAPH ALGORITHM; OPEN EAR DECOMPOSITION; PRAM MODEL; TIME ANALYSIS;
D O I：
10.1016/0167-8191(93)90071-R
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We present a parallel algorithm for a novel problem in a graph's open ear decomposition. The algorithm runs in O(log n) time with n processors on a CREW PRAM, where n is the number of vertices and m is the number of edges in the graph. We apply this result in parallel algorithms to solve the two vertex disjoint s-t paths problem in O(log n) time with n + m processors and the maximal path problem in planar graphs in O(log2 n) time with O(n) processors. Both of these algorithms run on the CRCW PRAM.
引用
收藏
页码：873 / 886
页数：14
相关论文
共 50 条
12345