Computer Science – Data Structures and Algorithms
Scientific paper
2011-05-12
Computer Science
Data Structures and Algorithms
31 pages
Scientific paper
We present two on-line 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(m^{3/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 {\em locality} property. Our second algorithm handles an arbitrary sequence of arc additions in $O(n^{5/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 $\Omega(n^2 2^{\sqrt{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 $\Theta(n^2 \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.
Haeupler Bernhard
Kavitha Telikepalli
Mathew Rogers
Sen Siddhartha
Tarjan Robert Endre
No associations
LandOfFree
Incremental Cycle Detection, Topological Ordering, and Strong Component Maintenance does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Incremental Cycle Detection, Topological Ordering, and Strong Component Maintenance, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Incremental Cycle Detection, Topological Ordering, and Strong Component Maintenance will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-496715