Skip to main content

Incremental Cycle Detection, Topological Ordering, and Strong Component Maintenance

Author(s): Haeupler, Bernhard; Kavitha, Telikepalli; Mathew, Rogers; Sen, Siddhartha; Tarjan, Robert E

To refer to this page use:
Abstract: We present two online algorithms for maintaining a topological order of a directed n-vertex acyclic graph as arcs are added, and detecting a cycle when one is created. Our first algorithm handles m arc additions in O(m3/2) time. For sparse graphs (m/n = O(1)), this bound improves the best previous bound by a logarithmic factor, and is tight to within a constant factor among algorithms satisfying a natural locality property. Our second algorithm handles an arbitrary sequence of arc additions in O(n5/2) time. For sufficiently dense graphs, this bound improves the best previous bound by a polynomial factor. Our bound may be far from tight: we show that the algorithm can take Ω(n22√2 lg n) time by relating its performance to a generalization of the k-levels problem of combinatorial geometry. A completely different algorithm running in Θ(n2 log n) time was given recently by Bender, Fineman, and Gilbert. We extend both of our algorithms to the maintenance of strong components, without affecting the asymptotic time bounds.
Publication Date: Jan-2012
Citation: Haeupler, Bernhard, Telikepalli Kavitha, Rogers Mathew, Siddhartha Sen, and Robert E. Tarjan. "Incremental Cycle Detection, Topological Ordering, and Strong Component Maintenance." ACM Transactions on Algorithms 8, no. 1 (2012): 3:1-3:33. doi:10.1145/2071379.2071382
DOI: 10.1145/2071379.2071382
ISSN: 1549-6325
EISSN: 1549-6333
Pages: 3:1 - 3:33
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.