Faster exact algorithms for computing Steiner trees in higher dimensional Euclidean spaces
Research output: Contribution to conference › Paper › Research
Standard
Faster exact algorithms for computing Steiner trees in higher dimensional Euclidean spaces. / Fonseca, Rasmus; Brazil, Marcus; Winter, Pawel; Zachariasen, Martin.
2014. Paper presented at 11th DIMACS Implementation Challenge, Providence, United States.Research output: Contribution to conference › Paper › Research
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - CONF
T1 - Faster exact algorithms for computing Steiner trees in higher dimensional Euclidean spaces
AU - Fonseca, Rasmus
AU - Brazil, Marcus
AU - Winter, Pawel
AU - Zachariasen, Martin
N1 - Conference code: 11
PY - 2014
Y1 - 2014
N2 - The Euclidean Steiner tree problem asks for a network of minimum total length interconnecting a finite set of points in d-dimensional space. For d ≥ 3, only one practical algorithmic approach exists for this problem --- proposed by Smith in 1992. A number of refinements of Smith's algorithm have increased the range of solvable problems a little, but it is still infeasible to solve problem instances with more than around 17 terminals. In this paper we firstly propose some additional improvements to Smith's algorithm. Secondly, we propose a new algorithmic paradigm called branch enumeration. Our experiments show that branch enumeration has similar performance as an optimized version of Smith's algorithm; furthermore, we argue that branch enumeration has the potential to push the boundary of solvable problems further.
AB - The Euclidean Steiner tree problem asks for a network of minimum total length interconnecting a finite set of points in d-dimensional space. For d ≥ 3, only one practical algorithmic approach exists for this problem --- proposed by Smith in 1992. A number of refinements of Smith's algorithm have increased the range of solvable problems a little, but it is still infeasible to solve problem instances with more than around 17 terminals. In this paper we firstly propose some additional improvements to Smith's algorithm. Secondly, we propose a new algorithmic paradigm called branch enumeration. Our experiments show that branch enumeration has similar performance as an optimized version of Smith's algorithm; furthermore, we argue that branch enumeration has the potential to push the boundary of solvable problems further.
KW - Faculty of Science
KW - Steiner tree problem
KW - d-dimensional Euclidean space
KW - exact algorithm
KW - computational study
M3 - Paper
T2 - 11th DIMACS Implementation Challenge
Y2 - 4 December 2014 through 5 December 2014
ER -
ID: 137038070