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

Fonseca, R, Brazil, M, Winter, P & Zachariasen, M 2014, 'Faster exact algorithms for computing Steiner trees in higher dimensional Euclidean spaces', Paper presented at 11th DIMACS Implementation Challenge, Providence, United States, 04/12/2014 - 05/12/2014. <http://dimacs11.zib.de/workshop/FonsecaBrazilWinterZachariasen.pdf>

APA

Fonseca, R., Brazil, M., Winter, P., & Zachariasen, M. (2014). Faster exact algorithms for computing Steiner trees in higher dimensional Euclidean spaces. Paper presented at 11th DIMACS Implementation Challenge, Providence, United States. http://dimacs11.zib.de/workshop/FonsecaBrazilWinterZachariasen.pdf

Vancouver

Fonseca R, Brazil M, Winter P, Zachariasen M. Faster exact algorithms for computing Steiner trees in higher dimensional Euclidean spaces. 2014. Paper presented at 11th DIMACS Implementation Challenge, Providence, United States.

Author

Fonseca, Rasmus ; Brazil, Marcus ; Winter, Pawel ; Zachariasen, Martin. / Faster exact algorithms for computing Steiner trees in higher dimensional Euclidean spaces. Paper presented at 11th DIMACS Implementation Challenge, Providence, United States.20 p.

Bibtex

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

}

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