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

An efficient parallel algorithm for the transitive closure of a graph

โœ Scribed by P. Fraisse

Publisher
Elsevier Science
Year
1986
Tongue
English
Weight
377 KB
Volume
6
Category
Article
ISSN
0164-1212

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

A Fully Dynamic Algorithm for Maintainin
A Fully Dynamic Algorithm for Maintaining the Transitive Closure
โœ Valerie King; Garry Sagert ๐Ÿ“‚ Article ๐Ÿ“… 2002 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 170 KB

This paper presents an efficient fully dynamic graph algorithm for maintaining the transitive closure of a directed graph. The algorithm updates the adjacency matrix of the transitive closure with each update to the graph; hence, each reachability query of the form ''Is there a directed path from i

An Efficient Parallel Algorithm for Maxi
An Efficient Parallel Algorithm for Maximum Matching for Some Classes of Graphs
โœ I. Parfenoff ๐Ÿ“‚ Article ๐Ÿ“… 1998 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 403 KB

The P 4 -tidy graphs were introduced by I. Rusu to generalize some already known classes of graphs with few induced P 4 (cographs, P 4 -sparse graphs, P 4 -lite graphs). Here, we propose an extension of R. Lin and S. Olariu's work (1994. J. Parallel Distributed Computing 22, 26 36.) on cographs, usi

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