A Dynamic Algorithm for Topologically Sorting Directed Acyclic Graphs
Author(s). David J. Pearce and Paul H.J. Kelly.
Venue. In Workshop on Efficient and experimental Algorithms (WEA), pages 383--398, 2004. ©Springer
Abstract: We consider how to maintain the topological order of a directed acyclic graph (DAG) in the presence of edge insertions and deletions. We present a new algorithm and, although this has marginally inferior time complexity compared with the best previously known result, we find that its simplicity leads to better performance in practice. In addition, we provide an empirical comparison against three alternatives over a large number of random DAG’s. The results show our algorithm is the best for sparse graphs and, surprisingly, that an alternative with poor theoretical complexity performs marginally better on dense graphs.