7 citations · 8 across the 4 of their papers we have counts for
4 papers
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(…
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…
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…
Linear-Time Pointer-Machine Algorithms for Path-Evaluation Problems on Trees and Graphs
Adam L. Buchsbaum, Loukas Georgiadis, Haim Kaplan +3
We present algorithms that run in linear time on pointer machines for a collection of problems, each of which either directly or indirectly requires the evaluation of a function de…