Better random sampling algorithms for flows in undirected graphs
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 value v in ~ O(pmnv) time. This improves on a previous bound of ~ O(m2=3n1=3v) given by the author recently, which in turn improved on the O(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 of v.