스타이너 트리를 이용한 입력 선분의 연결
Mechanism for Connecting Input Edges Using Steiner Tree
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
본 논문에서는 스타이너 트리를 이용하여 최소 길이로 입력 선분들을 모두 연결하는 방법을 제안한다. 선분은 통신선, 도로 및 철도망 또는 움직이는 물체의 궤적 등으로 변환될 수 있다. 본 논문에서 제안된 방법은 이러한 선분들을 최소 비용으로 연결하는 응용 등에 활용가능하다. 입력 선분의 수와 각 선분 당 최대 연결 선분의 수를 입력 인자로 설정한 실험 에서, 본 논문에서 제안된 방법은 최소 신장 트리를 이용한 방법과 비교하여 연결 생성 시간은 평균 192.0% 증가하였으나, 연결 길이는 평균 6.8%에 감소하였다. 이는 연결 방법을 찾는 시간보다는 연결 길이를 단축하는 것이 더 중요한 응용에 제안된 방법이 유용할 수 있음을 보인다.
Abstract
In this paper, a mechanism connecting all input edges with minimum length through Steiner tree is proposed. Edges are convertible into communication lines, roads, railroads or trace of moving object. Proposed mechanism could be applied to connect these edges with minimum cost. In our experiments where input edge number and maximum connections per edge are used as input parameters, our mechanism made connection length decrease average 6.8%, while building time for a connecting solution increase average 192.0% comparing with the method using minimum spanning tree. The result shows our mechanism might be well applied to the applications where connecting cost is more important than building time for a connecting solution.
참고문헌 (15)
- F.K. Hwang, "The Steiner Tree Problem", Annals of Discrete Mathematics, 53 (1992)
- W. Shi, "The Rectilinear Steiner Arborescence Problem is NP-Complete", Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, pp.780~787 (2000)
- R.L. Grahan, "On the History of the Minimum Spanning Tree Problem", Annals of the History of Computing, 7(1), pp.43~57
- T.H. Cormen, "Introduction to Algorithm, 2ndEd" (2001), MITPress
- 김인범, "선분상의 포탈을 이용한 근사 선분 최소 신장 트리의 생성", 정보처리학회논문지A, 16(6), pp.509~518 (2009), 한국정보처리학회
- A. Hayrapetyan, "Network Design for Information Networks", Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp.933~942 (2005)
- J. Kim, "A Polynomial Time Approximation Scheme for the Grade of Services Steiner Minimum Tree Problem", Journal of Global Optimization, 24, pp.437~448 (2002)
- 김재각, "원격 검침 시스템에서 근사 최소 스타이너 트리를 이용한 집중기 및 중계기의 효율적인 배치와 연결", 한국통신학회논문지B, 34(10), pp.994~1003 (2009), 한국통신학회
- 서민석, "스타이너 트리 문제를 위한 Max-Min Ant Colony Optimization", 경영과학, 26(1), pp.65~76 (2009), 한국경영과학회
- 이승관, "멀티캐스트 라우팅 문제 해결을 위한 엘리트 개미 시스템", 한국컴퓨터정보학회논문지, 13(3), pp.147~152 (2008), 한국컴퓨터정보학회
- 이성근, "다중 제약이 있는 멀티캐스트 트리 문제에 관한 연구", 인터넷정보학회논문지, 5(5), pp.129~138 (2004), 한국인터넷정보학회
- 김준모, "센서 네트워크 구축에서의 Combinatorial 기법 적용", 전자공학회논문지 - TC, 45(7), pp.9~16 (2008), 대한전자공학회
- "Steiner Minimal Tree Problem"[URL]