The GeoSteiner software package for computing Steiner trees in the plane: an updated computational study

Daniel Juhl; David M. Warme; Pawel Winter; Martin Zachariasen

The GeoSteiner software package for computing Steiner trees in the plane: an updated computational study

Daniel Juhl, David M. Warme, Pawel Winter, Martin Zachariasen

Datalogisk Institut

Abstract

The GeoSteiner software package has for more than 10 years been the fastest (publicly available) program for computing exact solutions to Steiner tree problems in the plane. The computational study by Warme, Winter and Zachariasen, published in 2000, documented the performance of the GeoSteiner approach --- allowing the exact solution of Steiner tree problems with more than a thousand terminals. Since then, a number of algorithmic enhancements have improved the performance of the software package significantly. In this computational study we run the current code on the largest problem instances from the 2000-study, and on a number of larger problem instances. The computational study is performed using both the publicly available GeoSteiner 3.1 code base, and the commercial GeoSteiner 4.0 code base.

Originalsprog	Engelsk
Publikationsdato	2014
Antal sider	30
Status	Udgivet - 2014
Begivenhed	11th DIMACS Implementation Challenge - ICERM, Providence, USA Varighed: 4 dec. 2014 → 5 dec. 2014 Konferencens nummer: 11

Konference

Konference	11th DIMACS Implementation Challenge
Nummer	11
Lokation	ICERM
Land/Område	USA
By	Providence
Periode	04/12/2014 → 05/12/2014

Emneord

Det Natur- og Biovidenskabelige Fakultet

Adgang til dokumentet

The GeoSteiner Software Package for Computing Steiner Trees in the Plane: An Updated Computational StudyAccepteret manuskript, 516 KB

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

Citationsformater

@conference{33ef119c99c945119455296ff28ee2eb,

title = "The GeoSteiner software package for computing Steiner trees in the plane: an updated computational study",

abstract = "The GeoSteiner software package has for more than 10 years been the fastest (publicly available) program for computing exact solutions to Steiner tree problems in the plane. The computational study by Warme, Winter and Zachariasen, published in 2000, documented the performance of the GeoSteiner approach --- allowing the exact solution of Steiner tree problems with more than a thousand terminals. Since then, a number of algorithmic enhancements have improved the performance of the software package significantly. In this computational study we run the current code on the largest problem instances from the 2000-study, and on a number of larger problem instances. The computational study is performed using both the publicly available GeoSteiner 3.1 code base, and the commercial GeoSteiner 4.0 code base. ",

keywords = "Faculty of Science, Euclidean Steiner tree problem, rectilinear Steiner tree problem, fixed orientation Steiner tree problem, exact algorithm, computational study",

author = "Daniel Juhl and Warme, {David M.} 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 - The GeoSteiner software package for computing Steiner trees in the plane

T2 - 11th DIMACS Implementation Challenge

AU - Juhl, Daniel

AU - Warme, David M.

AU - Winter, Pawel

AU - Zachariasen, Martin

N1 - Conference code: 11

PY - 2014

Y1 - 2014

N2 - The GeoSteiner software package has for more than 10 years been the fastest (publicly available) program for computing exact solutions to Steiner tree problems in the plane. The computational study by Warme, Winter and Zachariasen, published in 2000, documented the performance of the GeoSteiner approach --- allowing the exact solution of Steiner tree problems with more than a thousand terminals. Since then, a number of algorithmic enhancements have improved the performance of the software package significantly. In this computational study we run the current code on the largest problem instances from the 2000-study, and on a number of larger problem instances. The computational study is performed using both the publicly available GeoSteiner 3.1 code base, and the commercial GeoSteiner 4.0 code base.

AB - The GeoSteiner software package has for more than 10 years been the fastest (publicly available) program for computing exact solutions to Steiner tree problems in the plane. The computational study by Warme, Winter and Zachariasen, published in 2000, documented the performance of the GeoSteiner approach --- allowing the exact solution of Steiner tree problems with more than a thousand terminals. Since then, a number of algorithmic enhancements have improved the performance of the software package significantly. In this computational study we run the current code on the largest problem instances from the 2000-study, and on a number of larger problem instances. The computational study is performed using both the publicly available GeoSteiner 3.1 code base, and the commercial GeoSteiner 4.0 code base.

KW - Faculty of Science

KW - Euclidean Steiner tree problem

KW - rectilinear Steiner tree problem

KW - fixed orientation Steiner tree problem

KW - exact algorithm

KW - computational study

M3 - Paper

Y2 - 4 December 2014 through 5 December 2014

ER -

The GeoSteiner software package for computing Steiner trees in the plane: an updated computational study

Abstract

Konference

Emneord

Adgang til dokumentet

Fingeraftryk

Citationsformater