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.