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

Parallel Algorithms for Reducible Flow Graphs

โœ Scribed by Vijaya Ramachandran

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
324 KB
Volume
23
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

โœฆ Synopsis

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 of processors needed to multiply two n = n matrices in polylog time. We show that finding a minimum feedback vertex set in vertex-weighted rfg's or finding a minimum feedback arc set in arc-weighted rfg's is P-complete. For arc or vertex weights in unary, we present RNC algorithms for these problems and show that the problems are in NC if and only if the problem of finding a minimum cut in a flow network is in NC. แฎŠ 1997

Academic Press

The editors apologize for the delay in publication of this paper, for which the author is in no way responsible.

๐Ÿ“œ SIMILAR VOLUMES

Scalable parallel graph coloring algorit
Scalable parallel graph coloring algorithms
โœ Gebremedhin, Assefaw Hadish ;Manne, Fredrik ๐Ÿ“‚ Article ๐Ÿ“… 2000 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 143 KB ๐Ÿ‘ 1 views
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

A Randomized Parallel Algorithm for Plan
A Randomized Parallel Algorithm for Planar Graph Isomorphism
โœ Hillel Gazit; John H Reif ๐Ÿ“‚ Article ๐Ÿ“… 1998 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 223 KB

We present a parallel randomized algorithm running on a CRCW PRAM, to determine whether two planar graphs are isomorphic, and if so to find the isomorphism. We assume that we have a tree of separators for each planar graph ลฝ ลฝ 2 . 1 q โ‘€ which can be computed by known algorithms in O log n time with

A Parallel Algorithm for Lagrange Interp
A Parallel Algorithm for Lagrange Interpolation on the Star Graph
โœ H. Sarbazi-Azad; M. Ould-Khaoua; L.M. Mackenzie; S.G. Akl ๐Ÿ“‚ Article ๐Ÿ“… 2002 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 226 KB

This paper introduces a new parallel algorithm for computing an N(=n!)-point Lagrange interpolation on an n-star (n > 2). The proposed algorithm exploits several communication techniques on stars in a novel way, which can be adapted for computing similar functions. It is optimal and consists of thre