The search functionality is under construction.

The search functionality is under construction.

For the correctness of the minimum cut algorithm proposed in [H. Nagamochi and T. Ibaraki, Computing edge-connectivity of multigraphs and capacitated graphs, SIAM J. Discrete Mathematics, 5, 1992, pp. 54-66], 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*.

- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E82-A No.10 pp.2231-2236

- Publication Date
- 1999/10/25

- Publicized

- Online ISSN

- DOI

- Type of Manuscript
- PAPER

- Category
- Algorithms and Data Structures

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

Copy

Hiroshi NAGAMOCHI, Toshimasa ISHII, Toshihide IBARAKI, "A Simple Proof of a Minimum Cut Algorithm and Its Applications" in IEICE TRANSACTIONS on Fundamentals,
vol. E82-A, no. 10, pp. 2231-2236, October 1999, doi: .

Abstract: For the correctness of the minimum cut algorithm proposed in [H. Nagamochi and T. Ibaraki, Computing edge-connectivity of multigraphs and capacitated graphs, SIAM J. Discrete Mathematics, 5, 1992, pp. 54-66], 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*.

URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e82-a_10_2231/_p

Copy

@ARTICLE{e82-a_10_2231,

author={Hiroshi NAGAMOCHI, Toshimasa ISHII, Toshihide IBARAKI, },

journal={IEICE TRANSACTIONS on Fundamentals},

title={A Simple Proof of a Minimum Cut Algorithm and Its Applications},

year={1999},

volume={E82-A},

number={10},

pages={2231-2236},

abstract={For the correctness of the minimum cut algorithm proposed in [H. Nagamochi and T. Ibaraki, Computing edge-connectivity of multigraphs and capacitated graphs, SIAM J. Discrete Mathematics, 5, 1992, pp. 54-66], 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*.},

keywords={},

doi={},

ISSN={},

month={October},}

Copy

TY - JOUR

TI - A Simple Proof of a Minimum Cut Algorithm and Its Applications

T2 - IEICE TRANSACTIONS on Fundamentals

SP - 2231

EP - 2236

AU - Hiroshi NAGAMOCHI

AU - Toshimasa ISHII

AU - Toshihide IBARAKI

PY - 1999

DO -

JO - IEICE TRANSACTIONS on Fundamentals

SN -

VL - E82-A

IS - 10

JA - IEICE TRANSACTIONS on Fundamentals

Y1 - October 1999

AB - For the correctness of the minimum cut algorithm proposed in [H. Nagamochi and T. Ibaraki, Computing edge-connectivity of multigraphs and capacitated graphs, SIAM J. Discrete Mathematics, 5, 1992, pp. 54-66], 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*.

ER -