earticle

논문검색

최대 인접 병합 방법을 적용한 방향 그래프의 병목지점 탐색 알고리즘

원문정보

A Bottleneck Search Algorithm for Digraph Using Maximum Adjacency Merging Method

이상운

피인용수 : 0(자료제공 : 네이버학술정보)

초록

영어

Given digraph network D-(N,A), n∈N, a=c(u,v)∈A with source s and sink t, the maximum flow from to is determined by cut (S,T) that splits s∈S and t∈T disjoint sets with minimum cut value. The Ford-Fulkerson (F-F) algorithm with time complexity O(NA2) has been well known to this problem. The F-F algorithm finds all possible augmenting paths from to with residual capacity arcs and determines bottleneck arc that has a minimum residual capacity among the paths. After completion of algorithm, you should be determine the minimum cut by combination of bottleneck arcs. This paper suggests maximum adjacency merging and compute cut value method is called by MA-merging algorithm. We start the initial value to S={s}, T={t} Then we select the maximum capacity maxC(u,v) in the graph and merge to adjacent set or . Finally, we compute cut value of or . This algorithm runs times. We experiment Ford-Fulkerson and MA-merging algorithm for various 8 digraph. As a results, MA-merging algorithm can be finds minimum cut during the n-1 running times with time complexity O(N).

한국어

공급처 s와 수요처 t, 호가 수용량을 갖고 있는 방향 그래프 망 D=(N,A), n∈N, a=c(u,v)∈A에 대해, 공급처 s에서 수요처 t로의 최대 흐름양은 N을 s∈S와 t∈T의 집합으로 분리시키는 최소절단값이 결정한다. 최소절단을 찾는 대표적인 알고리즘으로는 수행복잡도 O(NA2)의 Ford-Fulkerson이 있다. 이 알고리즘은 가능한 모든 증대경로를 탐색하여 병목지점을 결정한다. 알고리즘이 종료되면 병목지점들의 조합으로 N-S+T의 절단이 되는 최소 절단을 결정해야 한다. 본 논문은 S={s}, T={t}를 초기값으로 설정하고, 망의 최대 수용량 호 maxC(u,v)를 인접한 S나 T로 병합시키고 절단값을 구하는 최대인접병합 알고리즘을 제안하였다. 최대인접병합 알고리즘은 n-1회를 수행하지만 알고리즘 수행 과정에서 최소절단을 찾는 장점을 갖고 있다. Ford-Fulkerson과 최대인접병합 알고리즘을 다양한 8개의 방향 그래프에 적용한 결과 제안된 알고리즘은 수행복잡도 O(N)인 n-1회 수행 과정에서 최소절단을 쉽게 찾을 수 있었다.

목차

요약
 Abstract
 Ⅰ. 서론
 Ⅱ. 관련 연구와 연구 배경
 Ⅲ. 최대인접병합 최소 절단 알고리즘
 Ⅳ. 알고리즘 적용 및 분석
 Ⅴ. 결론
 참고문헌

저자정보

  • 이상운 Sang-Un, Lee. 정회원, 강릉원주대학교 과학기술대학 멸티미디어공학과

참고문헌

자료제공 : 네이버학술정보

    함께 이용한 논문

      ※ 기관로그인 시 무료 이용이 가능합니다.

      • 4,200원

      0개의 논문이 장바구니에 담겼습니다.