A New Approach to Incremental Cycle Detection and Related Problems
Michael A. Bender, Jeremy T. Fineman, Seth Lewis Gilbert, Robert Endre Tarjan · ACM Transactions on Algorithms · 2015
We consider the problem of detecting a cycle in a directed graph that grows by arc insertions and the related problems of maintaining a topological order and the strong components of such a graph. For these problems, we give two algorithms, one suited to sparse graphs, the other to dense graphs. The former takes O (min { m 1/2 , n 2/3 } m ) time to insert m arcs into an n -vertex graph; the latter takes O ( n 2 log n ) time. Our sparse algorithm is substantially simpler than a previous O ( m 3/2 )-time algorithm; it is also faster on graphs of sufficient density. The time bound of our dense algorithm beats the previously best time bound of O ( n 5/2 ) for dense graphs. Our algorithms rely for their efficiency on vertex numberings weakly consistent with topological order: we allow ties. Bounds on the size of the numbers give bounds on running time.