#
Incremental Cycle Detection, Topological Ordering, and Strong Component
Maintenance

## Ross Wagner

This paper deals with maintaining the topological order for a directed
*n*-vertex acyclic graph as arcs are added to the graph as well as
detecting a cycle when one is created by adding a new arc. There are
two algorithms described in the paper, the first dealing with *m*
arc additions in O(*m*^{3/2}) time. This algorithm
improves the previous best bound by a logarithmic factor for sparse
networks and is within a constant factor among other algorithms
satisfying a natural locality property. The second algorithm has an
upper bound of O(*n*^{5/2}) time and a lower bound of
Ω(*n*^{2}2^{√2 log n})
obtained by relating its performance to a generalization of
the *k*-levels problem of combinatorial geometry.

(Based on a paper in
ACM Transactions on Algorithms 2012 by Bernhard Haeupler, Telikepalli
Kavitha, Rogers Mathew, Siddhartha Sen, and Robert Endre Tarjan.)