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

Publikation: KonferencebidragPaperForskning

Dokumenter

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.
OriginalsprogEngelsk
Publikationsdato2014
Antal sider20
StatusUdgivet - 2014
Begivenhed11th DIMACS Implementation Challenge - ICERM, Providence, USA
Varighed: 4 dec. 20145 dec. 2014
Konferencens nummer: 11

Konference

Konference11th DIMACS Implementation Challenge
Nummer11
LokationICERM
LandUSA
ByProvidence
Periode04/12/201405/12/2014

Antal downloads er baseret på statistik fra Google Scholar og www.ku.dk


Ingen data tilgængelig

ID: 137038070