A representation of cuts within 6/5 times the edge connectivity with applications
András A. Benczúr · 2002
Let G be an undirected c-edge connected graph. In this paper we give an O(n/sup 2/)-sized planar geometric representation for all edge cuts with capacity less than 6/5c. The representation can be very efficiently built, by using a single run of the Karger-Stein algorithm for finding near-mincuts. We demonstrate that the representation provides an efficient query structure for near-mincuts, as well as a new proof technique through geometric arguments. We show that in algorithms based on edge splitting, computing our representation O(log n) times substitute for one, or sometimes even /spl Omega/(n), u-/spl nu/ mincut computations; this can lead to significant savings, since our representation can be computed /spl theta//spl tilde/(m/n) times faster than the currently best known u-/spl nu/ mincut algorithm. We also improve the running time of the edge augmentation problem, provided the initial edge weights are polynomially bounded.