Faster exact algorithms for computing Steiner trees in higher dimensional Euclidean spaces
Research output: Contribution to conference › Paper › Research
Documents
- Fonseca_2015_Faster_exact_algorithms
Submitted manuscript, 453 KB, PDF document
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.
Original language | English |
---|---|
Publication date | 2014 |
Number of pages | 20 |
Publication status | Published - 2014 |
Event | 11th DIMACS Implementation Challenge - ICERM, Providence, United States Duration: 4 Dec 2014 → 5 Dec 2014 Conference number: 11 |
Conference
Conference | 11th DIMACS Implementation Challenge |
---|---|
Number | 11 |
Location | ICERM |
Country | United States |
City | Providence |
Period | 04/12/2014 → 05/12/2014 |
- Faculty of Science - Steiner tree problem, d-dimensional Euclidean space, exact algorithm, computational study
Research areas
Links
- http://dimacs11.zib.de/workshop/FonsecaBrazilWinterZachariasen.pdf
Submitted manuscript
Number of downloads are based on statistics from Google Scholar and www.ku.dk
No data available
ID: 137038070