병목 스타이너 트리의 정확한 해를 찾는 알고리즘

Abstract

본 논문에서는 병목 스타이너 트리의 정확한 해를 구하는 알고리즘을 다룬다. 병목 스타이너 트리 문제는 스타이너 트리중 가장 긴 간선의 길이가 최소화된 것을 구하는 문제이다. 이 문제는 √2이하의 근사율로 해를 구하는 것이 NP-Hard 일이 이미 증명되었다. 따라서 본 논문에서는 O(f(k)·nklogn) 시간에 정확한 해를 구하는 알고리즘을 제시한다. 여기서 n, k는 각각 주어진 점과 스타이너 점의 개수를 나타내며, f(k)는 k에만 관한 함수이다. 현재까지 이 문제에 대해서는 정확한 해를 구하는 알고리즘이 알려지지 않았고, 본 논문에서 처음으로 정확한 알고리즘을 제시한다.