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 条
  • [41] An overview of exact algorithms for the Euclidean Steiner tree problem in n-space
    Fampa, Marcia
    Lee, Jon
    Maculan, Nelson
    INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, 2016, 23 (05) : 861 - 874
  • [42] Baldwin effect and Lamarckian evolution in a memetic algorithm for Euclidean Steiner tree problem
    Michał Bereta
    Memetic Computing, 2019, 11 : 35 - 52
  • [43] On a Nonconvex MINLP Formulation of the Euclidean Steiner Tree Problem in n-Space
    D'Ambrosio, Claudia
    Fampa, Marcia
    Lee, Jon
    Vigerske, Stefan
    EXPERIMENTAL ALGORITHMS, SEA 2015, 2015, 9125 : 122 - 133
  • [44] Baldwin effect and Lamarckian evolution in a memetic algorithm for Euclidean Steiner tree problem
    Bereta, Michal
    MEMETIC COMPUTING, 2019, 11 (01) : 35 - 52
  • [45] An approximation algorithm for a bottleneck k-Steiner tree problem in the Euclidean plane
    Wang, LS
    Li, ZM
    INFORMATION PROCESSING LETTERS, 2002, 81 (03) : 151 - 156
  • [46] The Euclidean Bottleneck Steiner Path Problem
    Abu-Affash, A. Karim
    Carmi, Paz
    Katzi, Matthew J.
    Segal, Michael
    COMPUTATIONAL GEOMETRY (SCG 11), 2011, : 440 - 447
  • [47] AN ALGORITHM FOR THE STEINER PROBLEM IN THE EUCLIDEAN PLANE
    WINTER, P
    NETWORKS, 1985, 15 (03) : 323 - 345
  • [48] Fully Dynamic Algorithms for Euclidean Steiner Tree
    Chan, T-H Hubert
    Goranci, Gramoz
    Jiang, Shaofeng H-C
    Wang, Bo
    Xue, Quan
    WALCOM: ALGORITHMS AND COMPUTATION, WALCOM 2024, 2024, 14549 : 62 - 75
  • [49] On orientation metric and euclidean Steiner tree constructions
    Li, YY
    Leung, KS
    Wong, CK
    ISCAS '98 - PROCEEDINGS OF THE 1998 INTERNATIONAL SYMPOSIUM ON CIRCUITS AND SYSTEMS, VOLS 1-6, 1998, : E241 - E243
  • [50] Approximation algorithms for solving the 1-line Euclidean minimum Steiner tree problem
    Jianping Li
    Suding Liu
    Junran Lichen
    Wencheng Wang
    Yujie Zheng
    Journal of Combinatorial Optimization, 2020, 39 : 492 - 508