무방향 그래프의 최대인접병합 방법을 적용한 최소절단 알고리즘 (A Minimum Cut Algorithm Using Maximum Adjacency Merging Method of Undirected Graph)

서지정보

· 발행기관 : 한국인터넷방송통신학회
· 수록지 정보 : 한국인터넷방송통신학회 논문지 / 13권 / 1호 / 143 ~ 152페이지
· 저자명 : 최명복, 이상운

초록

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

영어초록

Given weighted graph , the minimum cut problem is classified with source and sink or without and . Given undirected weighted graph without and , 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 times. Given graph with and , Ford-Fulkerson algorithm determines the bottleneck edges in the arbitrary augmenting path from to . 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 and . This algorithm suggests MA-merging and computes cut value simultaneously. This algorithm runs times and successfully divides into disjoint and 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 processing times.

참고자료

· 없음