caa a22 4500 445805307 CHVBK 20180317145154.0 cr unu---uuuuu 170323e20111201xx s 000 0 eng 10.1007/s00453-011-9553-y doi (NATIONALLICENCE)springer-10.1007/s00453-011-9553-y Exact Algorithms for the Bottleneck Steiner Tree Problem [Elektronische Daten] [Sang Bae, Sunghee Choi, Chunseok Lee, Shin-ichi Tanigawa] Given n points, called terminals, in the plane ℝ2 and a positive integer k, the bottleneck Steiner tree problem is to find k Steiner points from ℝ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 ℝ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 1≤p≤∞, 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)⋅nlog 2 n time for the L 1 and the L ∞ metrics, and the first exact algorithm for the L p metric for any fixed rational p with 1<p<∞ whose time complexity is f(k)⋅(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. Springer Science+Business Media, LLC, 2011 Steiner point nationallicence Bottleneck Steiner tree nationallicence Exact algorithm nationallicence Fixed-parameter tractability nationallicence Computational geometry nationallicence Optimization nationallicence Bae Sang Department of Computer Science, Kyonggi University, Suwon, South Korea aut Choi Sunghee Division of Computer Science, KAIST, Daejeon, South Korea aut Lee Chunseok Division of Computer Science, KAIST, Daejeon, South Korea aut Tanigawa Shin-ichi Research Institute for Mathematical Sciences, Kyoto University, Kyoto, Japan aut Algorithmica Springer-Verlag 61/4(2011-12-01), 924-948 0178-4617 61:4<924 2011 61 453 https://doi.org/10.1007/s00453-011-9553-y text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-011-9553-y text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Bae Sang Department of Computer Science, Kyonggi University, Suwon, South Korea aut NATIONALLICENCE 700 1- Choi Sunghee Division of Computer Science, KAIST, Daejeon, South Korea aut NATIONALLICENCE 700 1- Lee Chunseok Division of Computer Science, KAIST, Daejeon, South Korea aut NATIONALLICENCE 700 1- Tanigawa Shin-ichi Research Institute for Mathematical Sciences, Kyoto University, Kyoto, Japan aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 61/4(2011-12-01), 924-948 0178-4617 61:4<924 2011 61 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer