Faster exact algorithms for computing Steiner trees in higher dimensional Euclidean spaces

Rasmus Fonseca; Marcus Brazil; Pawel Winter; Martin Zachariasen

Faster exact algorithms for computing Steiner trees in higher dimensional Euclidean spaces

Rasmus Fonseca, Marcus Brazil, Pawel Winter, Martin Zachariasen

Department of Computer Science

39 Downloads (Pure)

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 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/Territory	United States
City	Providence
Period	04/12/2014 → 05/12/2014

Keywords

Faculty of Science
Steiner tree problem
d-dimensional Euclidean space
exact algorithm
computational study

Access to Document

Fonseca_2015_Faster_exact_algorithmsSubmitted manuscript, 453 KB

http://dimacs11.zib.de/workshop/FonsecaBrazilWinterZachariasen.pdf

Cite this

@conference{df3345c1077d42fd87ba161e208d42c9,

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.",

keywords = "Faculty of Science, Steiner tree problem, d-dimensional Euclidean space, exact algorithm, computational study",

author = "Rasmus Fonseca and Marcus Brazil and Pawel Winter and Martin Zachariasen",

year = "2014",

language = "English",

note = "11th DIMACS Implementation Challenge ; Conference date: 04-12-2014 Through 05-12-2014",

}

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 -

Faster exact algorithms for computing Steiner trees in higher dimensional Euclidean spaces

Abstract

Conference

Keywords

Access to Document

Fingerprint

Cite this