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

Efficient Parallel Algorithms for Permutation Graphs

โœ Scribed by K. Arvind; V. Kamakoti; C.P. Rangan

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

No coin nor oath required. For personal study only.

โœฆ Synopsis

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 finding a Breadth First Search (BFS) spanning tree of a permutation graph rooted at vertex 1 and use the same to derive an efficient parallel algorithm for the All Pairs Shortest Path problem on permutation graphs. O 1995 Academic Press, Inc.

๐Ÿ“œ SIMILAR VOLUMES

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

An Optimal Shortest Path Parallel Algori
An Optimal Shortest Path Parallel Algorithm for Permutation Graphs
โœ O.H. Ibarra; Q. Zheng ๐Ÿ“‚ Article ๐Ÿ“… 1995 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 512 KB

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 f

Efficient Parallel Algorithms for Graphs
Efficient Parallel Algorithms for Graphs of Bounded Tree-Width
โœ Jens Lagergren ๐Ÿ“‚ Article ๐Ÿ“… 1996 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 236 KB

We present an efficient parallel algorithm for the tree-decomposition problem ลฝ 3 . ลฝ. for fixed width w. The algorithm runs in time O O log n and uses O O n processors on an ARBITRARY CRCW PRAM. The sequential complexity of our tree-decom-ลฝ 2 . position algorithm is O O n log n . The tree-decomposi

Parallel Algorithms for Reducible Flow G
Parallel Algorithms for Reducible Flow Graphs
โœ Vijaya Ramachandran ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 324 KB

We present parallel NC algorithms for recognizing a reducible flow graph rfg and for finding dominators, minimum feedback vertex sets, and a depth first search ลฝ . tree in an rfg. On an n-node rfg, all of these algorithms run in polylog n time ลฝ . ลฝ . using M n processors, where M n is the number o