SOLVING THE SHORTEST-PATHS PROBLEM ON BIPARTITE PERMUTATION GRAPHS EFFICIENTLY

被引：12

作者：

CHEN, L ^{[1
]}

机构：

[1] W COAST UNIV,DEPT COMP SCI,LOS ANGELES,CA 90020

来源：

INFORMATION PROCESSING LETTERS | 1995年 / 55卷 / 05期

关键词：

PARALLEL ALGORITHMS; SHORTEST PATHS; BIPARTITE PERMUTATION GRAPHS; UPPER AND LOWER BOUNDS;

D O I：

10.1016/0020-0190(95)00084-P

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

In this paper we present optimal sequential and parallel algorithms for the shortest-paths problems on strongly ordered bipartite (permutation) graphs. The parallel algorithm runs in O(log n) time on a CREW PRAM and is both time-optimal and work-optimal. With a published procedure as a subroutine, this work immediately leads to an optimal O(n(2)) time algorithm for the all-pairs shortest-paths problem on arbitrary bipartite permutation graphs.

引用

页码：259 / 264

页数：6

共 14 条

[1]

Akl S. G., 1989, DESIGN ANAL PARALLEL

[2]

AKL SG, 1989, 11TH P IFIP C SAN FR, P515

[3] OPTIMAL PARALLEL TIME-BOUNDS FOR THE MAXIMUM CLIQUE PROBLEM ON INTERVALS [J].