GeoSteiner

Software for Computing Steiner Trees

The GeoSteiner package solves the following NP-hard problems:

Euclidean Steiner Tree Problem in the Plane
Rectilinear Steiner Tree Problem in the Plane
Minimum Spanning Tree Problem in Hypergraphs

The code is written in ANSI C and requires no supplementary software or libraries. The code makes heavy use of linear programming (LP); the public domain LP-solver lp_solve is included (in a significantly modified form). However, the package also supports CPLEX, a proprietary product of the CPLEX division of ILOG Inc., which probably is the fastest and most robust LP-solver available.

Would you like to see a large Steiner tree? Here is the optimal solution for the 10000 point Euclidean instance in the OR-Library!

Authors

: David Warme, Emergent Information Technologies, Inc., Virginia, USA
: Pawel Winter, University of Copenhagen, Denmark
: Martin Zachariasen, University of Copenhagen, Denmark

Download

GeoSteiner 3.1

Unpack the downloaded (gzip'ed tar) file by using the command

gtar xzvf geosteiner-3.1.tar.gz

or by using the sequence of commands

gunzip geosteiner-3.1.tar.gz
tar xvf geosteiner-3.1.tar

Please read the LICENSE, README and INSTALL files carefully (in the given order).

Previous versions: GeoSteiner 3.0

Relevant Publications

Warme, D.M. Spanning Trees in Hypergraphs with Applications to Steiner Trees. Ph.D. Thesis, Computer Science Dept., The University of Virginia, 1998.

Winter, P. and Zachariasen, M. Euclidean Steiner Minimum Trees: An Improved Exact Algorithm. Networks 30, 149-166, 1997.

Zachariasen, M. Rectilinear Full Steiner Tree Generation. Networks 33, 125-143, 1999.

Warme, D. M., Winter, P. and Zachariasen, M. Exact Algorithms for Plane Steiner Tree Problems: A Computational Study. In D.Z. Du, J.M. Smith and J.H. Rubinstein (Eds.) Advances in Steiner Trees, pages 81-116, Kluwer Academic Publishers, 2000.

http://www.diku.dk/geosteiner/

martinz@diku.dk, January 7, 2003