ABSTRACT

The Steiner minimum tree (SMT) problem asks for a shortest network that spans a set of given points in a metric space. The set of given points are usually referred to as terminals and new auxiliary Steiner points can be introduced so that the total length of the network can be reduced. The history of the SMT problem started with Fermat (1601-1665) who proposed the

problem: given three points in a plane, find a fourth point such that the sum of its distances to the three given points is a minimum. Courant and Robbins [1] in their famous book What Is Mathematics? first named the problem after Steiner (1796-1863) who solved the problem of joining three villages by a system of roads having minimum total length. The popularity of this book has raised the research interests in the SMT problem. The formulation of the SMT problem is as follows.