A faster and simpler fully dynamic transitive closure
Author:
Open Access
- 28 March 2008
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 4 (1) , 1-16
Abstract
We obtain a new fully dynamic algorithm for maintaining the transitive closure of a directed graph. Our algorithm maintains the transitive closure matrix in a total running time of O ( mn + ( ins + del ) · n 2 ), where ins ( del ) is the number of insert (delete) operations performed. Here n is the number of vertices in the graph and m is the initial number of edges in the graph. Obviously, reachability queries can be answered in constant time. The algorithm uses only O ( n 2 ) time which is essentially optimal for maintaining the transitive closure matrix. Our algorithm can also support path queries. If v is reachable from u , the algorithm can produce a path from u to v in time proportional to the length of the path. The best previously known algorithm for the problem is due to Demetrescu and Italiano [2000]. Their algorithm has a total running time of O ( n 3 + ( ins + del ) · n 2 ). The query time is also constant. In addition, we also present a simple algorithm for directed acyclic graphs (DAGs) with a total running time of O ( mn + ins · n 2 + del ). Our algorithms are obtained by combining some new ideas with techniques of Italiano [1986, 1988], King [1999], King and Thorup [2001] and Frigioni et al. [2001]. We also note that our algorithms are extremely simple and can be easily implemented.Keywords
This publication has 4 references indexed in Scilit:
- Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths2002
- An Experimental Study of Dynamic Algorithms for Transitive ClosureACM Journal of Experimental Algorithmics, 2001
- A fully dynamic algorithm for maintaining the transitive closure1999
- Finding paths and deleting edges in directed acyclic graphsInformation Processing Letters, 1988