@article{fbf71d1489fa49708d3286cb67dd2e3d,
title = "A new approach to incremental cycle detection and related problems",
abstract = "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{m1/2, n2/3}m) time to insert m arcs into an n-vertex graph; the latter takes O(n2 log n) time. Our sparse algorithm is substantially simpler than a previous O(m3/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(n5/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.",
keywords = "Cycle detection, Incremental data structure, Strongly connected components, Topological ordering",
author = "Bender, {Michael A.} and Fineman, {Jeremy T.} and Seth Gilbert and Tarjan, {Robert E.}",
note = "Funding Information: This work was supported in part by the National Science Foundation, under grants CCF-0621439, CCF-0540897, CCF-0634793, CNS-0627645, CNS-1408695, CCF-1439084, IIS-1247726, IIS-1251137, CCF-1217708, and CCF-1114809, for M. A. Bender; CCF-1218188, CCF-1314633, and NSF/CRA-sponsored CIFellows program for J. T. Fineman; and CCF-0832797 for R. E. Tarjan. S. Gilbert was partially funded by MOE ARC-2 grant MOE2014-T2-1-157. R. E. Tarjan was also supported by the U.S.-Israel Binational Science Foundation, grant 2006204, and by the Distinguished Visitor program in the Stanford University Computer Science Department. The information contained herein does not necessarily reflect the opinion or policy of the federal government and no official endorsement should be inferred. We thank Don Knuth, who, during a presentation of a previous version of the sparse cycle detection algorithm, asked whether the algorithm really needed to use indices in addition to levels. The simplified algorithm presented in Section 2 demonstrates that the answer is no. We also thank Haim Kaplan for discussions leading to our presentation of Algorithm F as an improvement of Algorithm I. Publisher Copyright: {\textcopyright} 2015 ACM.",
year = "2015",
month = dec,
day = "1",
doi = "10.1145/2756553",
language = "English (US)",
volume = "12",
journal = "ACM Transactions on Algorithms",
issn = "1549-6325",
publisher = "Association for Computing Machinery (ACM)",
number = "2",
}