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

Improved Dynamic Reachability Algorithms for Directed Graphs

โœ Scribed by Roditty, Liam; Zwick, Uri

Book ID
118180732
Publisher
Society for Industrial and Applied Mathematics
Year
2008
Tongue
English
Weight
206 KB
Volume
37
Category
Article
ISSN
0097-5397

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

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

A Distributed Algorithm for GSPN Reachab
A Distributed Algorithm for GSPN Reachability Graph Generation
โœ S Caselli; G Conte; P Marenzoni ๐Ÿ“‚ Article ๐Ÿ“… 2001 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 318 KB

The applicability of generalized stochastic Petri nets (GSPNs) and other high-level modeling formalisms to real systems is often constrained by the explosion in the size of the underlying state-space representation. This paper describes a distributed program taking advantage of the large amount of m

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