On the Restricted 1-Steiner Tree Problem

被引：1
作者：
Bose, Prosenjit [1 ]
D'Angelo, Anthony [1 ]
Durocher, Stephane [2 ]
机构：
[1] Carleton Univ, Ottawa, ON K1S 5B6, Canada
[2] Univ Manitoba, Winnipeg, MB R3T 2N2, Canada
来源：
COMPUTING AND COMBINATORICS (COCOON 2020) | 2020年 / 12273卷
基金：
加拿大自然科学与工程研究理事会;
关键词：
Minimum k-Steiner tree; Steiner point restrictions; STEINER MINIMAL-TREES; ALGORITHMS; COMPLEXITY;
D O I：
10.1007/978-3-030-58150-3_36
中图分类号：
TP39 [计算机的应用];
学科分类号：
081203 ; 0835 ;
摘要：
Given a set P of n points in R-2 and an input line gamma, we present an algorithm that runs in optimal Theta(n log n) time and Theta(n) space to solve a restricted version of the 1-Steiner tree problem. Our algorithm returns a minimum-weight tree interconnecting P using at most one Steiner point s is an element of gamma where edges are weighted by the Euclidean distance between their endpoints.
引用
收藏
页码：448 / 459
页数：12
相关论文
共 41 条
  • [1] [Anonymous], 1985, Computational Geometry, DOI DOI 10.1007/978-1-4612-1098-6
  • [2] Aurenhammer F., 2013, VORONOI DIAGRAMS DEL, V8
  • [3] The LCA problem revisited
    Bender, MA
    Farach-Colton, M
    [J]. LATIN 2000: THEORETICAL INFORMATICS, 2000, 1776 : 88 - 94
  • [4] BOOTH RS, 1992, ALGORITHMICA, V7, P231, DOI 10.1007/BF01758760
  • [5] Approximating geometric bottleneck shortest paths
    Bose, P
    Maheshwari, A
    Narasimhan, G
    Smid, M
    Zeh, N
    [J]. COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2004, 29 (03): : 233 - 249
  • [6] On the complexity of the Steiner problem
    Brazil, M
    Thomas, DA
    Weng, JF
    [J]. JOURNAL OF COMBINATORIAL OPTIMIZATION, 2000, 4 (02) : 187 - 195
  • [7] Full minimal Steiner trees on lattice sets
    Brazil, M
    Rubinstein, JH
    Thomas, DA
    Weng, JF
    Wormald, NC
    [J]. JOURNAL OF COMBINATORIAL THEORY SERIES A, 1997, 78 (01) : 51 - 91
  • [8] Minimal Steiner trees for 2(k)x2(k) square lattices
    Brazil, M
    Cole, T
    Rubinstein, JH
    Thomas, DA
    Weng, JF
    Wormald, NC
    [J]. JOURNAL OF COMBINATORIAL THEORY SERIES A, 1996, 73 (01) : 91 - 110
  • [9] Minimal Steiner trees for rectangular arrays of lattice points
    Brazil, M
    Rubinstein, JH
    Thomas, DA
    Weng, JF
    Wormald, NC
    [J]. JOURNAL OF COMBINATORIAL THEORY SERIES A, 1997, 79 (02) : 181 - 208
  • [10] Brazil M., 2015, OPTIMAL INTERCONNECT, V29, DOI [10.1007/978-3- 319- 13915- 910.1007/978-3- 319- 13915-9, DOI 10.1007/978-3-319-13915-910.1007/978-3-319-13915-9]
12345