http://chineseinput.net/에서 pinyin(병음)방식으로 중국어를 변환할 수 있습니다.
변환된 중국어를 복사하여 사용하시면 됩니다.
배상원(Sang Won Bae),이춘석(Chunseok Lee),최성희(Sunghee Choi) 한국정보과학회 2009 한국정보과학회 학술발표논문집 Vol.36 No.1
본 논문에서는 병목 스타이너 트리의 정확한 해를 구하는 알고리즘을 다룬다. 병목 스타이너 트리 문제는 스타이너 트리중 가장 긴 간선의 길이가 최소화된 것을 구하는 문제이다. 이 문제는 √2이하의 근사율로 해를 구하는 것이 NP-Hard 임이 이미 증명되었다. 따라서 본 논문에서는 O(f(k) · n<SUP>k</SUP> log n)시간에 정확한 해를 구하는 알고리즘을 제시한다. 여기서 n,k는 각각 주어진 점과 스타이너 점의 개수를 나타내며, f(k)는 k에만 관한 함수이다. 현재까지 이 문제에 대해서는 정확한 해를 구하는 알고리즘이 알려지지 않았고, 본 논문에서 처음으로 정확한 알고리즘을 제시한다.