A Batch Algorithm for Maintaining a Topological Order
Author(s). David J. Pearce and Paul H.J. Kelly.
Venue. In Australasian Computer Science Conference (ACSC), pages 79--88, 2010. ©Australian Computer Society, Inc.
Abstract: The dynamic topological order problem is that of efficiently updating a topological order after some edge(s) are inserted into a graph. Much prior work exists on the unit-change version of this problem, where the order is updated after every single insertion. No previous (non-trivial) algorithms are known for the batch version of the problem, where the order is updated after every batch of insertions. We present the first such algorithm. This requires O(min{k · (v+e),ve}) time to process any sequence of k insertion batches. This is achieved by only recomputing those region(s) of the order affected by the inserted edges. In many cases, our algorithm will only traverse small portions of the graph when processing a batch. We empirically evaluate our algorithm against previous algorithms for this problem, and find that it performs well when the batch size is sufficiently large.