7 citations · 7 across the 3 of their papers we have counts for
3 papers
cs.DS2008★ 7 cited
Incremental Topological Ordering and Strong Component Maintenance
Bernhard Haeupler, Siddhartha Sen, Robert E. Tarjan
We present an on-line algorithm for maintaining a topological order of a directed acyclic graph as arcs are added, and detecting a cycle when one is created. Our algorithm takes O(…
cs.DS2007
Finding a Feasible Flow in a Strongly Connected Network
Bernhard Haeupler, Robert E. Tarjan
We consider the problem of finding a feasible single-commodity flow in a strongly connected network with fixed supplies and demands, provided that the sum of supplies equals the su…
cs.DS2007
Data Structures for Mergeable Trees
Loukas Georgiadis, Haim Kaplan, Nira Shafrir +2
Motivated by an application in computational topology, we consider a novel variant of the problem of efficiently maintaining dynamic rooted trees. This variant requires merging two…