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