The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
[H. Nagamochi and T. Ibaraki, Computing edge-connectivity of multigraphs and capacitated graphs, SIAM J. Discrete Mathematics, 5, 1992, pp. 54-66] 지금까지 몇 가지 간단한 증명이 제시되었습니다. 이 논문은 또 다른 간단한 증거를 제시합니다. 부산물로, 그것은 제공할 수 있습니다 O(m log n) 정점 쌍 사이의 최대 흐름을 출력하는 시간 알고리즘 s and t 알고리즘에 의해 선택됩니다. 여기서 n and m 각각 정점과 가장자리의 수입니다. 이 알고리즘은 DAG 계산 알고리즘의 속도를 높이는 데 사용될 수 있습니다.성 정점을 분리하는 모든 최소 컷을 나타냅니다. s and t 그래프에서 G, 그리고 선인장 Γ(를 계산하는 알고리즘G)는 모든 최소 컷을 나타냅니다. G.
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.
부
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 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e82-a_10_2231/_p
부
@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 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.},
keywords={},
doi={},
ISSN={},
month={October},}
부
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 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.
ER -