Computer Science – Data Structures and Algorithms
Scientific paper
2008-03-06
Computer Science
Data Structures and Algorithms
Scientific paper
We present an on-line algorithm for maintaining a topological order of a directed acyclic graph as arcs are added, and detecting a cycle when one is created. Our algorithm takes O(m^{1/2}) amortized time per arc, where m is the total number of arcs. For sparse graphs, this bound improves the best previous bound by a logarithmic factor and is tight to within a constant factor for a natural class of algorithms that includes all the existing ones. Our main insight is that the bidirectional search method of previous algorithms does not require an ordered search, but can be more general. This allows us to avoid the use of heaps (priority queues) entirely. Instead, the deterministic version of our algorithm uses (approximate) median-finding. The randomized version of our algorithm avoids this complication, making it very simple. We extend our topological ordering algorithm to give the first detailed algorithm for maintaining the strong components of a directed graph, and a topological order of these components, as arcs are added. This extension also has an amortized time bound of O(m^{1/2}) per arc.
Haeupler Bernhard
Sen Siddhartha
Tarjan Robert E.
No associations
LandOfFree
Incremental 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 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 Topological Ordering and Strong Component Maintenance will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-13473