검색 기능은 준비 중입니다.
검색 기능은 준비 중입니다.

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

A Simple Proof of a Minimum Cut Algorithm and Its Applications 최소절감 알고리즘과 그 응용에 대한 간단한 증명

Hiroshi NAGAMOCHI, Toshimasa ISHII, Toshihide IBARAKI

  • 조회수

    0

  • 이것을 인용

요약 :

[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.

발행
IEICE TRANSACTIONS on Fundamentals Vol.E82-A No.10 pp.2231-2236
발행일
1999/10/25
공개일
온라인 ISSN
DOI
원고의 종류
PAPER
범주
알고리즘 및 데이터 구조

작성자

키워드