Computer Science – Data Structures and Algorithms
Scientific paper
2010-10-14
Computer Science
Data Structures and Algorithms
Scientific paper
We introduce a new approach to computing an approximately maximum s-t flow in a capacitated, undirected graph. This flow is computed by solving a sequence of electrical flow problems. Each electrical flow is given by the solution of a system of linear equations in a Laplacian matrix, and thus may be approximately computed in nearly-linear time. Using this approach, we develop the fastest known algorithm for computing approximately maximum s-t flows. For a graph having n vertices and m edges, our algorithm computes a (1-\epsilon)-approximately maximum s-t flow in time \tilde{O}(mn^{1/3} \epsilon^{-11/3}). A dual version of our approach computes a (1+\epsilon)-approximately minimum s-t cut in time \tilde{O}(m+n^{4/3}\eps^{-8/3}), which is the fastest known algorithm for this problem as well. Previously, the best dependence on m and n was achieved by the algorithm of Goldberg and Rao (J. ACM 1998), which can be used to compute approximately maximum s-t flows in time \tilde{O}(m\sqrt{n}\epsilon^{-1}), and approximately minimum s-t cuts in time \tilde{O}(m+n^{3/2}\epsilon^{-3}).
Christiano Paul
Kelner Jonathan A.
Madry Aleksander
Spielman Daniel A.
Teng Shang-Hua
No associations
LandOfFree
Electrical Flows, Laplacian Systems, and Faster Approximation of Maximum Flow in Undirected Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Electrical Flows, Laplacian Systems, and Faster Approximation of Maximum Flow in Undirected Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Electrical Flows, Laplacian Systems, and Faster Approximation of Maximum Flow in Undirected Graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-285879