A New Approach to Incremental Cycle Detection and Related Problems

作者：Bender Michael A^*; Fineman Jeremy T^*; Gilbert Seth^*; Tarjan Robert E

来源：ACM Transactions on Algorithms, 2016, 12(2): 14.

DOI：10.1145/2756553

• Algorithms
• Theory
• Topological ordering
• cycle detection
• strongly connected components
• incremental data structure

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.

• 出版日期2016-2