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 条
  • [1] On the history of the Euclidean Steiner tree problem
    Brazil, Marcus
    Graham, Ronald L.
    Thomas, Doreen A.
    Zachariasen, Martin
    ARCHIVE FOR HISTORY OF EXACT SCIENCES, 2014, 68 (03) : 327 - 354
  • [2] The Euclidean Bottleneck Full Steiner Tree Problem
    A. Karim Abu-Affash
    Algorithmica, 2015, 71 : 139 - 151
  • [3] The Euclidean Bottleneck Full Steiner Tree Problem
    Abu-Affash, A. Karim
    ALGORITHMICA, 2015, 71 (01) : 139 - 151
  • [4] Two Heuristics for the Euclidean Steiner Tree Problem
    Derek R. Dreyer
    Michael L. Overton
    Journal of Global Optimization, 1998, 13 : 95 - 106
  • [5] Two heuristics for the Euclidean Steiner tree problem
    Dreyer, DR
    Overton, ML
    JOURNAL OF GLOBAL OPTIMIZATION, 1998, 13 (01) : 95 - 106
  • [6] On the Euclidean Bottleneck Full Steiner Tree Problem
    Abu-Affash, A. Karim
    COMPUTATIONAL GEOMETRY (SCG 11), 2011, : 433 - 439
  • [7] On Exact Solutions to the Euclidean Bottleneck Steiner Tree Problem
    Bae, Sang Won
    Lee, Chunseok
    Choi, Sunghee
    WALCOM: ALGORITHMS AND COMPUTATION, PROCEEDINGS, 2009, 5431 : 105 - 116
  • [9] A new heuristic for the Euclidean Steiner Tree Problem in Rn
    Pinto, Renan Vicente
    Maculan, Nelson
    TOP, 2023, 31 (02) : 391 - 413
  • [10] On exact solutions to the Euclidean bottleneck Steiner tree problem
    Bae, Sang Won
    Lee, Chunseok
    Choi, Sunghee
    INFORMATION PROCESSING LETTERS, 2010, 110 (16) : 672 - 678