| Computing the Minimum Cut and Maximum Flow of Undirected Graphs (2004) | |||||||||||||||||
Abstract | |||||||||||||||||
| Abstract This work presents an algorithm for computing the maximum flow and minimum cut of undirected graphs, based on the well-known algorithm presented by Ford and Fulkerson for directed graphs. The new algorithm is equivalent to just applying Ford and Fulkerson algorithm to the directed graph obtained from original graph but with two directed arcs for each edge in the graph, one in each way. We present a proof of correctness and experimental results. | |||||||||||||||||
Details der Publikation | |||||||||||||||||
| |||||||||||||||||