Earticle

초록

영어

Given weighted graph G = (V,E), n = IVI , m = IEI , the minimum cut problem is classified with source s and sink t or without s and t. Given undirected weighted graph without s and t, Stoer-Wagner algorithm is most popular. This algorithm fixes arbitrary vertex, and arranges maximum adjacency (MA)-ordering. In the last, the sum of weights of the incident edges for last ordered vertex is computed by cut value, and the last 2 vertices are merged. Therefore, this algorithm runs 2/n(n-1) times. Given graph with s and t, Ford-Fulkerson algorithm determines the bottleneck edges in the arbitrary augmenting path from s to t. If the augmenting path is no more exist, we determine the minimum cut value by combine the all of the bottleneck edges. This paper suggests minimum cut algorithm for undirected weighted graph with s and t. This algorithm suggests MA-merging and computes cut value simultaneously. This algorithm runs  n - 1 times and successfully divides V into disjoint S and V sets on the basis of minimum cut, but the Stoer-Wagner is fails sometimes. The proposed algorithm runs more than Ford-Fulkerson algorithm, but finds the minimum cut value within n - 1 processing times.

한국어

주어진 그래프 G = (V,E), n = IVI , m = IEI에 대해 최소절단을 찾는 연구는 공급처 s와 수요처 t가 주어지지 않은 경우와 주어진 경우로 구분된다. s와 t가 주어지지 않은 무방향 가중 그래프에 대한 Stoer-Wagner 알고리즘은 임의의 정점을 고정시키고 최대 인접 순서로 나열하여 마지막 정점의 절단 값과 마지막 2개 정점을 병합하면서 정점 을 축소시키는 방법으로 2/n(n-1) 회를 수행한다. 또한, s와 t가 주어진 그래프에 대한 Ford-Fulkerson 알고리즘은 증 대경로를 탐색하여 절단 간선을 결정한다. 더 이상의 증대 경로가 없으면 절단 간선들의 조합으로 최소절단을 결정해 야 한다. 본 논문은 단일 s와 t가 주어진 무방향 가중 그래프에 대해 최대인접 병합과 절단값을 동시에 계산하는 방법으로 n - 1회 수행으로 단축시켰다. 또한, Stoer-Wagner 알고리즘은 최소 절단을 기준으로 V = S + T로 양분하지 못 할 수 있는데 반해 제안된 알고리즘은 정확히 양분시켰다. 제안된 알고리즘은 Ford-Fulkerson의 증대경로를 찾는 수행 횟수보다 많이 수행하지만 수행과정에서 최소절단을 결정하는 장점이 있다.

목차

요약
 Abstract
 Ⅰ. 서론
 Ⅱ. 관련 연구와 연구 배경
  1. 최대 유동량/최소 절단 개념
  2. Stoer-Wagner 알고리즘
 Ⅲ. 최대인접병합 최소 절단 알고리즘
 Ⅳ. 알고리즘 적용 및 분석
 Ⅴ. 결론
 참고문헌

키워드

저자

• 최명복 [ Myeong-Bok Choi | 종신회원, 강릉원주대학교, 멀티미디어공학과 ]
• 이상운 [ Sang-Un Lee | 정회원, 강릉원주대학교 멀티미디어공학과 ] Corresponding Author

참고문헌

발행기관

간행물

표지보기 관심저널 등록

• 간행물명

  한국인터넷방송통신학회 논문지 [The Journal of the Institute of Internet, Broadcasting and Communication]

• 간기

  격월간

• pISSN

  2289-0238

• eISSN

  2289-0246

• 수록기간

  2001~2025

• 십진분류

  KDC 326 DDC 380