Euclidean Bottleneck Steiner Tree is Fixed-Parameter Tractable

被引：0

作者：

Bandyapadhyay, Sayan ^{[1
]}

Lochet, William ^{[2
]}

Lokshtanov, Daniel ^{[3
]}

Saurabh, Saket ^{[4
]}

Xue, Jie ^{[5
]}

机构：

[1] Portland State Univ, Portland, OR 97207 USA

[2] Univ Montpellier, CNRS, LIRMM, Montpellier, France

[3] Univ Calif Santa Barbara, Santa Barbara, CA 93106 USA

[4] Inst Math Sci, Chennai, Tamil Nadu, India

[5] New York Univ Shanghai, Shanghai, Peoples R China

来源：

PROCEEDINGS OF THE 2024 ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, SODA | 2024年

基金：

欧洲研究理事会;

关键词：

APPROXIMATION ALGORITHM; MINIMUM NUMBER;

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

In the Euclidean Bottleneck Steiner Tree problem, the input consists of a set of n points in R-2 called terminals and a parameter k, and the goal is to compute a Steiner tree that spans all the terminals and contains at most k points of R-2 as Steiner points such that the maximum edge-length of the Steiner tree is minimized, where the length of a tree edge is the Euclidean distance between its two endpoints. The problem is well-studied and is known to be NP-hard. In this paper, we give a k(O(k))n(O(1))-time algorithm for Euclidean Bottleneck Steiner Tree, which implies that the problem is fixed-parameter tractable (FPT). This settles an open question explicitly asked by Bae et al. [Algorithmica, 2011], who showed that the l(1) and l(infinity) variants of the problem are FPT. Our approach can be generalized to the problem with l(p) metric for any rational 1 <= p <= infinity, or even other metrics on R-2.

引用

页码：699 / 711

页数：13

共 39 条

[1] Bottleneck bichromatic full Steiner trees [J].