# 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
- Uniformly Oriented 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 ILOG division of
IBM
Inc., which is one of 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,
Group W, Inc., Virginia, USA
- Pawel Winter,
University of Copenhagen, Denmark
- Martin Zachariasen,
University of Southern Denmark, Denmark

### Download

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

gtar xzvf geosteiner-5.1.tar.gz

or by using the sequence of commands
gunzip geosteiner-5.1.tar.gz
tar xvf geosteiner-5.1.tar

Please read the
LICENSE,
README and
INSTALL files carefully
(in the given order).
Manual for latest version:
geosteiner-5.1-manual.pdf

Previous versions:
GeoSteiner 5.0.1
GeoSteiner 5.0
(GeoSteiner 4.0 was a commercial product.)
GeoSteiner 3.1
GeoSteiner 3.0

Steiner tree problem instances:
Problem Instances.

### 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.

Juhl, D., Warme, D. M., Winter, P. and Zachariasen, M.
The GeoSteiner Software Package for Computing Steiner Trees in the
Plane: An Updated Computational Study
(Paper presented at 11th DIMACS Implementation Challenge, Brown
University, December 2014. Updated version submitted for
publication.)

Brazil, M. and Zachariasen, M.
Optimal Interconnection Trees in the Plane:
Theory, Algorithms and Applications.
Springer.
Info available here.

http://www.geosteiner.com/
webmaster@geosteiner.com,
January 1, 2017