Premium
An overview of exact algorithms for the Euclidean Steiner tree problem in n ‐space
Author(s) -
Fampa Marcia,
Lee Jon,
Maculan Nelson
Publication year - 2016
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/itor.12207
Subject(s) - steiner tree problem , generalization , euclidean geometry , euclidean space , mathematics , algorithm , space (punctuation) , computer science , euclidean shortest path , mathematical optimization , shortest path problem , combinatorics , graph , longest path problem , mathematical analysis , geometry , operating system
The Euclidean Steiner tree problem (ESTP) in R n is to find a shortest network interconnecting p given points in n ‐dimensional Euclidean space. The problem was first described in the plane and an algorithm with very good practical efficiency has been proposed to solve this particular case. The generalization for higher dimensions was proposed in the 19th century, however the numerical solution of the problem remains very challenging when n ≥ 3 . We give an overview of the exact algorithms presented in the literature for the ESTP when n ≥ 3 and discuss their common and distinguished features, their advantages and drawbacks, and some possible directions for improvement toward the numerical solution of large instances of the problem.