
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

A Simple Proof of a Minimum Cut Algorithm and Its Applications
Hiroshi NAGAMOCHI Toshimasa ISHII Toshihide IBARAKI
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E82A
No.10
pp.22312236 Publication Date: 1999/10/25 Online ISSN:
DOI: Print ISSN: 09168508 Type of Manuscript: PAPER Category: Algorithms and Data Structures Keyword: graph, edgeconnectivity, minimum cut, flow, MAordering, dynamic tree structure,
Full Text: PDF(406.5KB)>>
Summary:
For the correctness of the minimum cut algorithm proposed in [H. Nagamochi and T. Ibaraki, Computing edgeconnectivity of multigraphs and capacitated graphs, SIAM J. Discrete Mathematics, 5, 1992, pp. 5466], 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 DAG_{s,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.

