Incremental Cycle Detection, Topological Ordering, and Strong Component Maintenance

Bernhard Haeupler, Telikepalli Kavitha, Rogers Mathew +2

We present two on-line algorithms for maintaining a topological order of a directed $n$-vertex acyclic graph as arcs are added, and detecting a cycle when one is created. Our first…