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.
본 논문에서는 입력 선분들 상에 위치하며, 이들을 일정한 길이로 분할하는 가상 노드 포탈을 이용하여 입력 선분들을 모두 연결하는 근사 선분 최소 신장 트리를 빠른 시간 내에 찾는 방법을 제안한다. 이 근사 선분 최소 신장 트리는 통신선, 도로 및 철도망의 연결 등에 활용될 수 있다. 3000개의 입력 선분에 대해 제안된 방법으로 생성된 근사 트리는, 포탈 간격이 0.3인 경우에 최적 선분 최소 신장 트리와 비교하여 1.8% 의 길이가 증가한 반면에 트리 생성 시간은 29.74%의 감소를 보였고, 0.75의 경우 2.96%의 길이의 증가와 39.96%의 트리 생성 시간의 절감을 보였다. 이는 약간의 길이 증가를 허용하면서 짧은 시간 내에 선분 연결 트리를 생성해야 하는 응용에 잘 적용될 수 있음을 보인다. 또한 제안 된 방법은 포탈 간격, 포탈 포기 비율 등을 외부 인자로서 조절하여, 목적에 따른 트리 길이 또는 트리 생성 시간에 중점을 둔 근사 선분 최소 신장 트리 생성이 가능함을 보인다.
