TY - GEN

T1 - Faster algorithms for incremental topological ordering

AU - Haeupler, Bernhard

AU - Kavitha, Telikepalli

AU - Mathew, Rogers

AU - Sen, Siddhartha

AU - Tarjan, Robert E.

PY - 2008/8/14

Y1 - 2008/8/14

N2 - We present two online algorithms for maintaining a topological order of a directed acyclic graph as arcs are added, and detecting a cycle when one is created. Our first algorithm takes O(m1/2) amortized time per arc and our second algorithm takes O(n2.5/m) amortized time per arc, where n is the number of vertices and m is the total number of arcs. For sparse graphs, our O(m1/2) bound improves the best previous bound by a factor of log n 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 two-way search method of previous algorithms does not require an ordered search, but can be more general, allowing us to avoid the use of heaps (priority queues). Instead, the deterministic version of our algorithm uses (approximate) median-finding; the randomized version of our algorithm uses uniform random sampling. For dense graphs, our O(n2.5/m) bound improves the best previously published bound by a factor of n1/4 and a recent bound obtained independently of our work by a factor of log n. Our main insight is that graph search is wasteful when the graph is dense and can be avoided by searching the topological order space instead. Our algorithms extend to the maintenance of strong components, in the same asymptotic time bounds.

AB - We present two online algorithms for maintaining a topological order of a directed acyclic graph as arcs are added, and detecting a cycle when one is created. Our first algorithm takes O(m1/2) amortized time per arc and our second algorithm takes O(n2.5/m) amortized time per arc, where n is the number of vertices and m is the total number of arcs. For sparse graphs, our O(m1/2) bound improves the best previous bound by a factor of log n 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 two-way search method of previous algorithms does not require an ordered search, but can be more general, allowing us to avoid the use of heaps (priority queues). Instead, the deterministic version of our algorithm uses (approximate) median-finding; the randomized version of our algorithm uses uniform random sampling. For dense graphs, our O(n2.5/m) bound improves the best previously published bound by a factor of n1/4 and a recent bound obtained independently of our work by a factor of log n. Our main insight is that graph search is wasteful when the graph is dense and can be avoided by searching the topological order space instead. Our algorithms extend to the maintenance of strong components, in the same asymptotic time bounds.

UR - http://www.scopus.com/inward/record.url?scp=49049084644&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=49049084644&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-70575-8_35

DO - 10.1007/978-3-540-70575-8_35

M3 - Conference contribution

AN - SCOPUS:49049084644

SN - 3540705740

SN - 9783540705741

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 421

EP - 433

BT - Automata, Languages and Programming - 35th International Colloquium, ICALP 2008, Proceedings

T2 - 35th International Colloquium on Automata, Languages and Programming, ICALP 2008

Y2 - 7 July 2008 through 11 July 2008

ER -