Earticle

초록

영어

The min-cut problem that decides the maximum flow in a complex network flows from source(s) to sink(t) is known as a hard problem. The augmenting path algorithm divides into single path and decides the bottleneck point(edge), but the min-cut section to be decide additionally. This paper suggests O(n) time complexity heuristic greedy algorithm for the number of vertices n that applies free agent system in a pro-sports field. The free agent method assumes NG(S), NG(T) vertices among v∈V ╲{s,t} to free agent players, and this players transfer into the team that suggest more annual income. As a result of various networks, this algorithm can be finds all of min-cut sections and min-cut value for whole cases.

한국어

공급지(s)에서 수요지(t)로 흐르는 복잡한 망에서 망의 최대 흐름을 결정하는 최소절단 면을 찾는 최소절단 문제 는 난제로 알려져 있다. 이에 대해 증대경로 알고리즘은 증대경로를 갖는 단일 경로로 분할하여 병목 지점(간선)을 찾는 방식을 채택하고 있으나 최소절단면을 추가적으로 결정해야만 한다. 본 논문에서는 프로스포츠계에서 적용되고 있는 자 유계약제 방식을 적용하여, 정점 수 n에 대해 수행 복잡도가 O(n)인 휴리스틱 탐욕 알고리즘을 제안한다. 자유계약 방 식은 ν∈V ╲{s,t} 정점들 중에서 NG(S),NG(T) 정점들을 자유계약 선수라고 가정하고, 이 선수들의 연봉이 보다 상승하 는 팀으로 이적하는 방식을 적용하였다. 제안된 알고리즘을 다양한 망 형태에 적용한 결과, 모든 망에서 최소절단 치 뿐 아니라 망에 존재하는 모든 최소절단 들을 찾을 수 있음을 보였다.

목차

요약
Abstract
Ⅰ. 서론
Ⅱ. 관련 연구와 문제점
Ⅲ. 자유계약 알고리즘
Ⅳ. 알고리즘 적용 및 결과 분석
Ⅴ. 결론
References

키워드

저자

• 이상운 [ 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