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

A Fully Dynamic Algorithm for Maintaining the Transitive Closure

โœ Scribed by Valerie King; Garry Sagert

Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
170 KB
Volume
65
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

โœฆ Synopsis

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 to j?'' can be answered in O(1) time. The algorithm is randomized and has a onesided error; it is correct when answering yes, but has O(1/n c ) probability of error when answering no, for any constant c. In acyclic graphs, worst case update time is O(n 2 ). In general graphs, the update time is O(n 2.26 ). The space complexity of the algorithm is O(n 2 ).

๐Ÿ“œ SIMILAR VOLUMES

Fully Dynamic Algorithms for Maintaining
Fully Dynamic Algorithms for Maintaining Shortest Paths Trees
โœ Daniele Frigioni; Alberto Marchetti-Spaccamela; Umberto Nanni ๐Ÿ“‚ Article ๐Ÿ“… 2000 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 213 KB

We propose fully dynamic algorithms for maintaining the distances and the shortest paths from a single source in either a directed or an undirected graph with positive real edge weights, handling insertions, deletions, and weight updates of edges. The algorithms require linear space and optimal quer

A new set of channel allocation algorith
A new set of channel allocation algorithms providing a smooth transition from fully dynamic to totally fixed
โœ Ailton A. Shinoda; Michel D. Yacoub ๐Ÿ“‚ Article ๐Ÿ“… 1999 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 132 KB

A set of three allocation algorithms is proposed and analysed. As opposed to a number of allocation algorithms, whose performance is greatly dependent on the traffic profile, these techniques are dynamically adaptable to the change of the traffic load, combining the features of dynamic channel alloc

A dynamic algorithm for integration in t
A dynamic algorithm for integration in the boundary element method
โœ Bruce A. Ammons; Madhukar Vable ๐Ÿ“‚ Article ๐Ÿ“… 1998 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 182 KB ๐Ÿ‘ 3 views

The discretization of the boundary in boundary element method generates integrals over elements that can be evaluated using numerical quadrature that approximate the integrands or semi-analytical schemes that approximate the integration path. In semi-analytical integration schemes, the integration p