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

Rasmus Fonseca, Marcus Brazil, Pawel Winter, Martin Zachariasen

Research output: Contribution to conferencePaperpeer-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
Number of pages20
Publication statusPublished - 2014
EventDIMACS Implementation Challenge - ICERM, Providence, United States
Duration: 4 Dec 20145 Dec 2014
Conference number: 11

Conference

ConferenceDIMACS Implementation Challenge
Country/TerritoryUnited States
CityProvidence
Period4/12/145/12/14

Keywords

  • Steiner tree problem
  • d-dimensional Euclidean space
  • exact algorithm
  • computational study

Fingerprint

Dive into the research topics of 'Faster exact algorithms for computing Steiner trees in higher dimensional Euclidean spaces'. Together they form a unique fingerprint.

Cite this