๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

An Optimal Shortest Path Parallel Algorithm for Permutation Graphs

โœ Scribed by O.H. Ibarra; Q. Zheng

Publisher
Elsevier Science
Year
1995
Tongue
English
Weight
512 KB
Volume
24
Category
Article
ISSN
0743-7315

No coin nor oath required. For personal study only.

โœฆ Synopsis

We present an optimal parallel algorithm for the single-source shortest path problem for permutation graphs. The algorithm runs in (O(\log n)) time using (O(n / \log n)) processors on an EREW PRAM. As an application, we show that a minimum connected dominating set in a permutation graph can be found in (O(\log n)) time using (O(n / \log n)) processors. O 1995 Academic Press, Inc.

๐Ÿ“œ SIMILAR VOLUMES

Termination Detection for Parallel Short
Termination Detection for Parallel Shortest Path Algorithms
โœ Michelle R Hribar; Valerie E Taylor; David E Boyce ๐Ÿ“‚ Article ๐Ÿ“… 1998 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 322 KB

Shortest path computation is required by a large number of applications such as VLSI, transportation, and communication networks. These applications, which are often very complex and have sparse networks, generally use parallel labeling shortest path algorithms. Such algorithms, when implemented on

Efficient Parallel Algorithms for Permut
Efficient Parallel Algorithms for Permutation Graphs
โœ K. Arvind; V. Kamakoti; C.P. Rangan ๐Ÿ“‚ Article ๐Ÿ“… 1995 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 641 KB

In this paper, we present optimal \(O(\log n)\) time, \(O(n / \log n)\) processor EREW PRAM parallel algorithms for finding the connected components, cut vertices, and bridges of a permutation graph. We also present an \(O(\log n)\) time, \(O(n)\) processor, CREW PRAM model parallel algorithm for fi

Faster Shortest-Path Algorithms for Plan
Faster Shortest-Path Algorithms for Planar Graphs
โœ Monika R Henzinger; Philip Klein; Satish Rao; Sairam Subramanian ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 445 KB

We give a linear-time algorithm for single-source shortest paths in planar graphs with nonnegative edge-lengths. Our algorithm also yields a linear-time algorithm for maximum flow in a planar graph with the source and sink on the same face. For the case where negative edge-lengths are allowed, we gi

Efficient parallel algorithms for bipart
Efficient parallel algorithms for bipartite permutation graphs
โœ Lin Chen; Yaacov Yesha ๐Ÿ“‚ Article ๐Ÿ“… 1993 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 858 KB

## Abstract In this paper, we further study the properties of bipartite permutation graphs. We give first efficient parallel algorithms for several problems on bipartite permutation graphs. These problems include transforming a bipartite graph into a strongly ordered one if it is also a permutation