CS 269S, Spring 2012: Theory Seminar
Bren Hall, Room 1420
April 27, 2012:

Incremental Cycle Detection, Topological Ordering, and Strong Component Maintenance

Ross Wagner

This paper deals with maintaining the topological order for a directed n-vertex acyclic graph as arcs are added to the graph as well as detecting a cycle when one is created by adding a new arc. There are two algorithms described in the paper, the first dealing with m arc additions in O(m3/2) time. This algorithm improves the previous best bound by a logarithmic factor for sparse networks and is within a constant factor among other algorithms satisfying a natural locality property. The second algorithm has an upper bound of O(n5/2) time and a lower bound of Ω(n22√2 log n) obtained by relating its performance to a generalization of the k-levels problem of combinatorial geometry.

(Based on a paper in ACM Transactions on Algorithms 2012 by Bernhard Haeupler, Telikepalli Kavitha, Rogers Mathew, Siddhartha Sen, and Robert Endre Tarjan.)