Faster Exact Algorithms for Computing Steiner Trees in Higher Dimensional Euclidean Spaces

Rasmus Fonseca, Marcus Brazil, Pawel Winter, Martin Zachariasen

Research output: Contribution to conference without publisher/journalPaperResearchpeer-review

Abstract

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 languageEnglish
Publication date4. Dec 2014
Number of pages20
Publication statusPublished - 4. Dec 2014
Externally publishedYes

Fingerprint

Experiments

Cite this

Fonseca, R., Brazil, M., Winter, P., & Zachariasen, M. (2014). Faster Exact Algorithms for Computing Steiner Trees in Higher Dimensional Euclidean Spaces.
Fonseca, Rasmus ; Brazil, Marcus ; Winter, Pawel ; Zachariasen, Martin. / Faster Exact Algorithms for Computing Steiner Trees in Higher Dimensional Euclidean Spaces. 20 p.
@conference{9489584d810847a8a479e99ef59722db,
title = "Faster Exact Algorithms for Computing Steiner Trees in Higher Dimensional Euclidean Spaces",
abstract = "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.",
author = "Rasmus Fonseca and Marcus Brazil and Pawel Winter and Martin Zachariasen",
year = "2014",
month = "12",
day = "4",
language = "English",

}

Faster Exact Algorithms for Computing Steiner Trees in Higher Dimensional Euclidean Spaces. / Fonseca, Rasmus; Brazil, Marcus; Winter, Pawel; Zachariasen, Martin.

2014.

Research output: Contribution to conference without publisher/journalPaperResearchpeer-review

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

PY - 2014/12/4

Y1 - 2014/12/4

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.

M3 - Paper

ER -