186 citations · 243 across the 28 of their papers we have counts for
Showing 2011 · cs.DSShow all
2 papers · 2 filters
cs.DS2011★ 1 cited
A New Approach to Incremental Cycle Detection and Related Problems
Michael A. Bender, Jeremy T. Fineman, Seth Gilbert +1
We consider the problem of detecting a cycle in a directed graph that grows by arc insertions, and the related problems of maintaining a topological order and the strong components…
cs.DS2011★ 6 cited
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 -vertex acyclic graph as arcs are added, and detecting a cycle when one is created. Our first…