Better random sampling algorithms for flows in undirected graphs
David R. Karger · 1998
We present better random sampling algorithms for maximum flows in undirected graphs. Our algorithms apply to capacitated or uncapacitated graphs, and find a maximum flow of valuevin~O(pmnv)time. This improves on a previous bound of~O(m2=3n1=3v)given by the author recently, which in turn improved on theO(mv)time bound for a typical augmenting path algorithm. In uncapacitated graphs without parallel edges, the bound is no worse than~O(n5=2). We give another algorithm that finds a(1�)times maximum flow in time~O(mpn=), regardless ofv. 1 Introduction. Random sampling has been a useful tool for solving cut problems in undirected graphs. In previous work [Kar97a], this author showed that randomly choosing edges from a