EFFICIENT PARALLEL ALGORITHMS FOR PERMUTATION GRAPHS

Authors
ARVIND K KAMAKOTI V RANGAN CP
Citation
K. Arvind et al., EFFICIENT PARALLEL ALGORITHMS FOR PERMUTATION GRAPHS, Journal of parallel and distributed computing, 26(1), 1995, pp. 116-124
Citations number
4
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods
Journal title
Journal of parallel and distributed computing → ACNP
ISSN journal
07437315
Volume
26
Issue
1
Year of publication
1995
Pages
116 - 124
Database
ISI
SICI code
0743-7315(1995)26:1<116:EPAFPG>2.0.ZU;2-3
Abstract
In this paper, we present optimal O(log n) time, O(n/log n) processor EREW PRAM parallel algorithms for finding the connected components, cu t vertices, and bridges of a permutation graph. We also present an O(l og n) time, O(n) processor, CREW PRAM model parallel algorithm for fin ding a Breadth First Search (BFS) spanning tree of a permutation graph rooted at vertex 1 and use the same to derive an efficient parallel a lgorithm for the All Pairs Shortest Path problem on permutation graphs . (C) 1995 Academic Press, Inc.