James R. Russell, Robert E. Strom, et al.
ACM SIGPLAN Notices
In this paper we present an algorithm for solving two problems in dynamically maintaining the transitive closure of a digraph: In the first problem a sequence of edge insertions is performed on an initially empty graph, interspersed with p transitive closure queries of the form: "is there a path from a to b in the graph". Our algorithm solves this problem in time O (dm*+p), where d is the maximum outdegree of the resulting graph G and m* is the number of edges in the transitive closure of G. In the second problem, a sequence of edge deletions is performed on an acyclic graph, interspersed with p transitive closure queries. Once again we solve this problem in time O (dm*+p), where d is the maximum outdegree of the initial graph G and m* is the number of edges in the transitive closure of G. For bounded degree graphs, this improves upon previous results. Our algorithms also work when insertions and deletions to the graph are intermixed. Finally, we show how to implement the operation findpath (x, y) which retrieves some path from x to y in time proportional to the length of the path. © 1993 Springer-Verlag.
James R. Russell, Robert E. Strom, et al.
ACM SIGPLAN Notices
Daniel M. Yellin, Jorge Buenabad-Chávez, et al.
ICDEW 2008
Daniel M. Yellin, Robert E. Strom
ACM Transactions on Programming Languages and Systems (TOPLAS)
Robert E. Strom, Daniel M. Yellin
IEEE Transactions on Software Engineering