ICS 269, Spring 1997: Theory Seminar
30 May 1997:
Using Random Sampling to Find Maximum Flows
Dan Halem, ICS, UC Irvine
We present new algorithms, based on random sampling, that find
maximum flows in undirected uncapcitated graphs. Our algorithms
dominate augmenting paths over all parameter values (number of
vertices and edges and flow value). They also dominate blocking
flows over a large range of parameter values. Furthermore, they
achieve time bounds on graphs with parallel (equivalently,
capacitated) edges that previously could only be achieved on graphs
without them.
From a STOC '97
paper by David
Karger.