A First Experimental Study of a Dynamic Transitive Closure Algorithm
Tobias Miller, Christos Zaroliagis · 1997
We describe an implementation of Italiano's partially dynamic data structure for maintaining transitive closure information in a directed graph and report on experimental results with random directed graphs and random sequences of operations. The operations supported are edge insertions or edge deletions, and queries. For the case of edge deletions the directed graph is assumed to be acyclic. 1. Introduction Dynamic graph algorithms maintain a certain property (e.g., connectivity) of a graph that changes dynamically over time. Typical changes include insertion of a new edge and deletion of an existing edge. The challenge for a dynamic algorithm is to maintain, in an environment of dynamic changes, the desired graph property efficiently, i.e., without recomputing everything from scratch after a dynamic change. Dynamic graph algorithms have been an active and blossoming field over the last years. A number of important theoretical results (especially for undirected graphs) have been achi...