A New Approach to Incremental Cycle Detection and Topological Ordering

Feb 2, 2011

ABSTRACT:
This talk considers the problem of detecting a cycle in a directed
graph that grows dynamically by arc insertions, and the related
problem of maintaining a topological ordering of such a graph. For
this problem, we give two algorithms, one suited to sparse graphs and
the other to dense graphs. The former takes O(m^{3/2}) time to insert
m arcs into an n-vertex graph; the latter takes O(n^2 log n) time.
The best previous data structure also achieves the O(m^{3/2}) bound
for sparse graphs, but our algorithm is considerably simpler. The time
bound of our dense algorithm significantly beats the previously best
time bound of O(n^{5/2}). At the heart of both our algorithms is a new
approach for maintaining the incremental topological ordering. Instead
of placing vertices in an ordered list that explicitly represents the
topological ordering, we assign labels to each vertex; the labels
induce a topological ordering and can be updated efficiently as arcs
are inserted.

This talk represents joint work with Michael A. Bender, Seth Gilbert, and Robert E. Tarjan.

This talk represents joint work with Michael A. Bender, Seth Gilbert, and Robert E. Tarjan.