- 최소 지름 신장 트리를 구하는 근사 알고리즘
- ㆍ 저자명
- 신찬수,박상민
- ㆍ 간행물명
- 정보과학회논문지. Journal of KIISE. 시스템 및 이론
- ㆍ 권/호정보
- 2003년|30권 5호|pp.319-323 (5 pages)
- ㆍ 발행정보
- 한국정보과학회
- ㆍ 파일정보
- 정기간행물| PDF텍스트
- ㆍ 주제분야
- 기타
이 논문은 한국과학기술정보연구원과 논문 연계를 통해 무료로 제공되는 원문입니다.
이차원 평면에 주어진 n개의 점 집합 P에 대한, 최소 신장 트리(minimum spanning tree, MST)는 P의 점들을 연결한 신장 트리 중에서 에지 길이의 총합이 최소가 되는 트리로 정의된다. P에 대한 신장 트리의 지름(diameter)은 트리의 두 점을 연결한 트리 경로 중에서 최장 경로의 길이로 정의되며, 최소 지름 신장 트리(minimum-diameter spanning tree, MDST)는 P에 대한 신장 트리 중에서 지름이 가장 작은 트리를 의미한다. 현재까지 알려진 가장 좋은 알고리즘[3]은 MDST를 O(n$^3$) 시간에 구한다. 본 논문에서는 MDST의 지름보다 최대 5/4배 이내의 지름을 보장하는 신장 트리를 구하는 $O(n^2)$ 시간 근사 알고리즘(approximation algorithm)을 제시한다. 이것은 MDST 문제에 관한 첫 번째 근사 알고리즘이다.
Let P be a set of n points in the plane. A minimum spanning tree(MST) is a spanning tree connecting n points of P such that the sum of lengths of edges of the tree is minimized. A diameter of a tree is the maximum length of paths connecting two points of a spanning tree of P. The problem considered in this paper is to compute the spanning tree whose diameter is minimized over all spanning trees of P. We call such tree a minimum-diameter spanning tree(MDST). The best known previous algorithm[3] finds MDST in $O(n^2)$ time. In this paper, we suggest an approximation algorithm to compute a spanning tree whose diameter is no more than 5/4 times that of MDST, running in O(n$^2$log$^2$n) time. This is the first approximation algorithm on the MDST problem.