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

A parallel search algorithm for directed acyclic graphs

โœ Scribed by Ratan K. Ghosh; G. P. Bhattacharjee

Publisher
Springer Netherlands
Year
1984
Tongue
English
Weight
860 KB
Volume
24
Category
Article
ISSN
0006-3835

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

Shortest path algorithms for nearly acyc
Shortest path algorithms for nearly acyclic directed graphs
โœ Tadao Takaoka ๐Ÿ“‚ Article ๐Ÿ“… 1998 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 496 KB

Abuaiadh and Kingston gave an efficient algorithm for the single source shortest path problem for a nearly acyclic graph with O(m + n log t) computing time, where m and n are the numbers of edges and vertices of the given directed graph and t is the number of delete-min operations in the priority qu

Parallelism, Preprocessing, and Reachabi
Parallelism, Preprocessing, and Reachability: A Hybrid Algorithm for Directed Graphs
โœ P.N. Klein ๐Ÿ“‚ Article ๐Ÿ“… 1993 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 602 KB

The problem of reachability in a directed graph has resisted attempts at efficient parallelization. Only for fairly dense graphs can we efficiently achieve significant parallel speedups, using known methods. We describe a technique allowing significant parallel speedup even for moderately sparse gra

Searching for acyclic orientations of gr
Searching for acyclic orientations of graphs
โœ Martin Aigner; Eberhard Triesch; Zsolt Tuza ๐Ÿ“‚ Article ๐Ÿ“… 1995 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 397 KB

We want to find an unknown acyclic orientation ~\* of an (undirected) graph G by testing for certain edges how they are oriented according to ~\*. How many tests do we need in the worst case? We give upper and lower bounds for this number c(G) in terms of the independence number of G and study the c