Skip to main content

A New Approach to Incremental Cycle Detection and Related Problems

Author(s): Bender, Michael A; Fineman, Jeremy T; Gilbert, Seth; Tarjan, Robert E

To refer to this page use:
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(n2log 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.
Publication Date: Dec-2015
Citation: Bender, Michael A., Jeremy T. Fineman, Seth Gilbert, and Robert E. Tarjan. "A New Approach to Incremental Cycle Detection and Related Problems." ACM Transactions on Algorithms 12, no. 2 (2015): pp. 14:1-14:22. doi:10.1145/2756553
DOI: 10.1145/2756553
ISSN: 1549-6325
EISSN: 1549-6333
Pages: 14:1 - 14:22
Type of Material: Journal Article
Journal/Proceeding Title: ACM Transactions on Algorithms
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.