병목 스타이너 트리의 정확한 해를 찾는 알고리즘An Exact Algorithm for the Euclidean Bottleneck Steiner Tree Problem

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

Korea Computer Congress (한국컴퓨터종합학술대회) 2009, v.36, no.1, pp.371 - 376

URI
http://hdl.handle.net/10203/162286
Appears in Collection
CS-Conference Papers(학술회의논문)
Files in This Item
There are no files associated with this item.

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0