- 링 네트워크에서의 최대 다품종정수흐름문제와 최소 다중절단면문제에 대한 해법
- ㆍ 저자명
- 명영수,Myung. Young-Soo
- ㆍ 간행물명
- 韓國經營科學會誌
- ㆍ 권/호정보
- 2007년|32권 2호|pp.89-97 (9 pages)
- ㆍ 발행정보
- 한국경영과학회
- ㆍ 파일정보
- 정기간행물| PDF텍스트
- ㆍ 주제분야
- 기타
이 논문은 한국과학기술정보연구원과 논문 연계를 통해 무료로 제공되는 원문입니다.
We study the maximum integer multiflow problem and the minimum multicut problem in a ring network. Both problems in a general network are known to be NP-hard. In this paper, we develop polynomial time algorithms to solve the problems. We also prove that even In a ring network, maximum multiflow is not always integral, which implies that the amount of maximum integer flow does not always reach the minimum capacity of multicut.