On the history of the Euclidean Steiner tree problem

被引:0
|
作者
Marcus Brazil
Ronald L. Graham
Doreen A. Thomas
Martin Zachariasen
机构
[1] The University of Melbourne,Department of Electrical and Electronic Engineering
[2] UC San Diego,Department of Computer Science and Engineering
[3] The University of Melbourne,Department of Mechanical Engineering
[4] University of Copenhagen,Department of Computer Science
来源
Archive for History of Exact Sciences | 2014年 / 68卷
关键词
Fermat; Minimum Span Tree; Equilateral Triangle; Steiner Tree; Steiner Point;
D O I
暂无
中图分类号
学科分类号
摘要
The history of the Euclidean Steiner tree problem, which is the problem of constructing a shortest possible network interconnecting a set of given points in the Euclidean plane, goes back to Gergonne in the early nineteenth century. We present a detailed account of the mathematical contributions of some of the earliest papers on the Euclidean Steiner tree problem. Furthermore, we link these initial contributions with results from the recent literature on the problem.
引用
收藏
页码:327 / 354
页数:27
相关论文
共 50 条
  • [21] Solving the prize-collecting Euclidean Steiner tree problem
    Whittle, David
    Brazil, Marcus
    Grossman, Peter A.
    Rubinstein, J. Hyam
    Thomas, Doreen A.
    INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, 2022, 29 (03) : 1479 - 1501
  • [22] The Euclidean Steiner tree problem in Rn: A mathematical programming formulation
    Nelson Maculan
    Philippe Michelon
    Adilson E. Xavier
    Annals of Operations Research, 2000, 96 : 209 - 220
  • [23] Approximation algorithm for bottleneck Steiner tree problem in the Euclidean plane
    Zi-Mao Li
    Da-Ming Zhu
    Shao-Han Ma
    Journal of Computer Science and Technology, 2004, 19 : 791 - 794
  • [24] The Euclidean bottleneck Steiner tree and Steiner tree with minimum number of Steiner points
    Du, DZ
    Wang, LS
    Xu, BA
    COMPUTING AND COMBINATORICS, 2001, 2108 : 509 - 518
  • [25] Solving the degree-constrained Euclidean Steiner minimal tree problem
    Dong Shujuan
    ADVANCED RESEARCH ON INFORMATION SCIENCE, AUTOMATION AND MATERIAL SYSTEM, PTS 1-6, 2011, 219-220 : 652 - 655
  • [26] A randomized Delaunay triangulation heuristic for the Euclidean Steiner tree problem in ℜd
    Jon W. Van Laarhoven
    Jeffrey W. Ohlmann
    Journal of Heuristics, 2011, 17 : 353 - 372
  • [27] Nearly optimal solution for restricted euclidean bottleneck Steiner tree problem
    Li, Zimao
    Xiao, Wenying
    Journal of Networks, 2014, 9 (04) : 1000 - 1004
  • [28] Concatenation-Based Greedy Heuristics for the Euclidean Steiner Tree Problem
    M. Zachariasen
    P. Winter
    Algorithmica, 1999, 25 : 418 - 437
  • [29] A Flow-Dependent Quadratic Steiner Tree Problem in the Euclidean Plane
    Brazil, Marcus N.
    Ras, Charl J.
    Thomas, Doreen A.
    NETWORKS, 2014, 64 (01) : 18 - 28
  • [30] Concatenation-based greedy heuristics for the Euclidean Steiner tree problem
    Zachariasen, M
    Winter, P
    ALGORITHMICA, 1999, 25 (04) : 418 - 437