ICS Theory Group

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.