A simple proof of a minimum cut algorithm and its applications

A simple proof of a minimum cut algorithm and its applications

0.00 Avg rating0 Votes
Article ID: iaor2001947
Country: Japan
Volume: E83-A
Issue: 10
Start Page Number: 2231
End Page Number: 2236
Publication Date: Oct 1999
Journal: Transactions of the Institute of Electronics, Information and Communication Engineers
Authors: , ,
Keywords: networks: flow
Abstract:

For the correctness of the minimum cut algorithm proposed by Nagamochi and Ibaraki, several simple proofs have been presented so far. This paper gives yet another simple proof. As a byproduct, it can provide an O(m log n) time algorithm that outputs a maximum flow between the pair of vertices s and t selected by the algorithm, where n and m are the numbers of vertices and edges, respectively. This algorithm can be used to speed up the algorithm to compute DAGs,t that represents all minimum cuts separating vertices s and t in a graph G, and the algorithm to compute the cactus Γ(G) that represents all minimum cuts in G.

Reviews

Required fields are marked *. Your email address will not be published.