선분상의 포탈을 이용한 근사 선분 최소 신장 트리의 생성
Mechanism for Building Approximation Edge Minimum Spanning Tree Using Portals on Input Edges
0
조회
0
다운로드
3
인용
0
참고문헌
키워드
초록
본 논문에서는 입력 선분들 상에 위치하며, 이들을 일정한 길이로 분할하는 가상 노드 포탈을 이용하여 입력 선분들을 모두 연결하는 근사 선분 최소 신장 트리를 빠른 시간 내에 찾는 방법을 제안한다. 이 근사 선분 최소 신장 트리는 통신선, 도로 및 철도망의 연결 등에 활용될 수 있다. 3000개의 입력 선분에 대해 제안된 방법으로 생성된 근사 트리는, 포탈 간격이 0.3인 경우에 최적 선분 최소 신장 트리와 비교하여 1.8%의 길이가 증가한 반면에 트리 생성 시간은 29.74%의 감소를 보였고, 0.75의 경우 2.96%의 길이의 증가와 39.96%의 트리 생성 시간의 절감을 보였다. 이는 약간의 길이 증가를 허용하면서 짧은 시간 내에 선분 연결 트리를 생성해야 하는 응용에 잘 적용될 수 있음을 보인다. 또한 제안된 방법은 포탈 간격, 포탈 포기 비율 등을 외부 인자로서 조절하여, 목적에 따른 트리 길이 또는 트리 생성 시간에 중점을 둔 근사 선분 최소 신장 트리 생성이 가능함을 보인다.
Abstract
In this paper, a mechanism that produces an approximation edges minimum spanning tree swiftly using virtual nodes called portals dividing given edges into same distance sub-edges. The approximation edges minimum spanning tree can be used in many useful areas as connecting communication lines, road networks and railroad systems. For 3000 random input edges, when portal distance is 0.3, tree building time decreased 29.74% while the length of the produced tree increased 1.8% comparing with optimal edge minimum spanning tree in our experiment. When portal distance is 0.75, tree building time decreased 39.96% while the tree length increased 2.96%. The result shows this mechanism might be well applied to the applications that may allow a little length overhead, but should produce an edge connecting tree in short time. And the proposed mechanism can produce an approximation edge minimum spanning tree focusing on tree length or on building time to meet user requests by adjusting portal distance or portal discard ratio as parameter.
참고문헌 (14)
- 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, 2nd Ed" (2001), MIT Press
- F.P. Preparata, "Computational Geometry: an Introduction" (1985), Springer-Verlag
- K.W. Chong, "Concurrent threads and optimal parallel minimum spanning trees algorithm", Journal of the ACM, 48, pp.297~323 (2001)
- S. Pettie, "An Optimal Minimum Spanning Tree Algorithm", Journal of the ACM, 49, pp.16~34 (2002)
- D.R. Karger, "A randomized linear-time algorithm to find minimum spanning trees", Journal of the ACM, 42, pp.321~328 (1995)
- M. Ahuja, "A distributed algorithm for minimum weight spanning trees based on echo algorithms", 9th International Conference on Distributed Computing Systems, pp.2~8 (1989)
- J.M. Ho, "Minimum Diameter Spanning Trees and Related Problems", SIAM Journal on Computing, 20(5), pp.987~997 (1991)
- J. Gudmundsson, "Approximating the Geometric Minimum-Diameter Spanning Tree", APPROX 2002, 통권 : 2462, pp.146~160 (2002)
- C. Monmna, "Transitions in Geometric Spanning Trees", Transitions in Geometric Spanning Trees, 8(1), pp.265~293 (1992)
- K.M. Chandy, "The Capacitated minimum spanning tree", Networks, 3, pp.173~182 (1973)
- "Steiner Minimal Tree Problem"[URL]
- 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)