Exact Algorithms for the Bottleneck Steiner Tree Problem

被引：9

作者：

Bae, Sang Won ^{[1
]}

Choi, Sunghee ^{[2
]}

Lee, Chunseok ^{[2
]}

Tanigawa, Shin-ichi ^{[3
]}

机构：

[1] Kyonggi Univ, Dept Comp Sci, Suwon, South Korea

[2] Korea Adv Inst Sci & Technol, Div Comp Sci, Taejon 305701, South Korea

[3] Kyoto Univ, Math Sci Res Inst, Kyoto, Japan

来源：

ALGORITHMICA | 2011年 / 61卷 / 04期

基金：

日本学术振兴会; 新加坡国家研究基金会;

关键词：

Steiner point; Bottleneck Steiner tree; Exact algorithm; Fixed-parameter tractability; Computational geometry; Optimization; APPROXIMATION ALGORITHM; COMPUTATION;

D O I：

10.1007/s00453-011-9553-y

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

Given n points, called terminals, in the plane a"e(2) and a positive integer k, the bottleneck Steiner tree problem is to find k Steiner points from a"e(2) and a spanning tree on the n+k points that minimizes its longest edge length. Edge length is measured by an underlying distance function on a"e(2), usually, the Euclidean or the L (1) metric. This problem is known to be NP-hard. In this paper, we study this problem in the L (p) metric for any 1a parts per thousand currency signpa parts per thousand currency signa, and aim to find an exact algorithm which is efficient for small fixed k. We present the first fixed-parameter tractable algorithm running in f(k)a <...nlog (2) n time for the L (1) and the L (a) metrics, and the first exact algorithm for the L (p) metric for any fixed rational p with 1 < p < a whose time complexity is f(k)a <...(n (k) +nlog n), where f(k) is a function dependent only on k. Note that prior to this paper there was no known exact algorithm even for the L (2) metric.

引用

页码：924 / 948

页数：25

共 29 条

[1]

ABELLANAS M, 2006, 002 RHEIN F WILH U B

[2] SORTING IN C LOG N PARALLEL STEPS [J].