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 条
  • [31] Evolutionary Approach to the Euclidean Steiner Tree Problem in n-Space
    Bereta, Michal
    APPLIED SCIENCES-BASEL, 2025, 15 (03):
  • [32] A randomized Delaunay triangulation heuristic for the Euclidean Steiner tree problem in Rd
    Van Laarhoven, Jon W.
    Ohlmann, Jeffrey W.
    JOURNAL OF HEURISTICS, 2011, 17 (04) : 353 - 372
  • [33] A Genetic Algorithm Approach for the Euclidean Steiner Tree Problem with Soft Obstacles
    Rosenberg, Manou
    French, Tim
    Reynolds, Mark
    While, Lyndon
    PROCEEDINGS OF THE 2021 GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE (GECCO'21), 2021, : 618 - 626
  • [34] Aggregating robots compute:: An adaptive heuristic for the Euclidean Steiner tree problem
    Hamann, Heiko
    Woern, Heinz
    FROM ANIMALS TO ANIMATS 10, PROCEEDINGS, 2008, 5040 : 447 - 456
  • [35] Mixed integer nonlinear optimizationmodels for the Euclidean Steiner tree problem in Rd
    Ouzia, Hacene
    Maculan, Nelson
    JOURNAL OF GLOBAL OPTIMIZATION, 2022, 83 (01) : 119 - 136
  • [36] Conversion of the Steiner Problem on the Euclidean Plane to the Steiner Problem on Graph
    D. T. Lotarev
    A. P. Uzdemir
    Automation and Remote Control, 2005, 66 : 1603 - 1613
  • [37] Conversion of the Steiner problem on the euclidean plane to the Steiner problem on graph
    Lotarev, DT
    Uzdemir, AP
    AUTOMATION AND REMOTE CONTROL, 2005, 66 (10) : 1603 - 1613
  • [38] A dynamic adaptive relaxation scheme applied to the Euclidean Steiner minimal tree problem
    Chapeau-Blondeau, F
    Janez, F
    Ferrier, JL
    SIAM JOURNAL ON OPTIMIZATION, 1997, 7 (04) : 1037 - 1053
  • [39] A hybrid evolutionary algorithm for the Euclidean Steiner tree problem using local searches
    Yang, Byounghak
    KNOWLEDGE-BASED INTELLIGENT INFORMATION AND ENGINEERING SYSTEMS, PT 1, PROCEEDINGS, 2006, 4251 : 60 - 67
  • [40] Iterated local search algorithms for the Euclidean Steiner tree problem in n dimensions
    do Forte, Vinicius Leal
    Tavares Montenegro, Flavio Marcelo
    de Moura Brito, Jose Andre
    Maculan, Nelson
    INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, 2016, 23 (06) : 1185 - 1199