
	Minimizing a network's length is one of the oldest optimization
	problems in mathematics and, consequently, it has been worked
	on by many of the leading mathematicians in history.  In the
	mid-seventeenth century a simple problem was posed:  Find the
	point $P$ that minimizes the sum of the distances from $P$ to
	each of three given points in the plane.  Solutions to this
	problem were derived independently by Fermat, Torricelli and
	Cavalieri.  They all deduced that either $P$ is inside the
	triangle formed by the given points and that the angles at $P$
	formed by the lines joining $P$ to the three points are all
	$120^{\circ}$, or $P$ is one of the three vertices and the
	angle at $P$ formed by the lines joining $P$ to the other two
	points is greater than or equal to $120^{\circ}$.

	In the nineteenth century a mathematician at the University of
	Berlin, named Jakob Steiner, studied this problem and generalized
	it to include an arbitrarily large set of points in the plane.
	This generalization created a star when $P$ was connected to
	all the given points in the plane, and is a geometric approach
	to the 2-dimensional center of mass problem.

	In 1934 K\"{o}ssler and Jarn\'{i}k generalized the network
	minimization problem even further~\cite{jk34:omgodb}:  Given
	$n$ points in the plane find the shortest possible connected
	network containing these points.  This generalized problem,
	however, did not become popular until the book, {\it What is
	Mathematics}, by Courant and Robbins~\cite{cr41:wim}, appeared
	in 1941. Courant and Robbins linked the name Steiner with this
	form of the problem proposed by K\"{o}ssler and Jarn\'{i}k, and
	it became known as the Steiner Minimal Tree problem.  The
	general solution to this problem allows multiple points to be
	added, each of which is called a Steiner Point, creating a tree
	instead of a star.

	Much is known about the exact solution to the Steiner Minimal
	Tree problem.  Those who wish to learn about some of the
	spin-off problems are invited to read the introductory article
	by Bern and Graham~\cite{bg89:tsnp}, the excellent survey paper
	on this problem by Hwang and Richards~\cite{hr92:survey}, or
	the recent volume in The Annals of Discrete Mathematics devoted
	completely to Steiner Tree problems~\cite{hrw:annals}.  Some of
	the basic pieces of information about the Steiner Minimal Tree
	problem that can be gleaned from these articles are: (i) the
	fact that all of the original $n$ points will be of degree 1,
	2, or 3, (ii) the Steiner Points are all of degree 3, (iii) any
	two edges meet at an angle of at least $120^{\circ}$ in the
	Steiner Minimal Tree, and (iv) at most $n-2$ Steiner Points
	will be added to the network.

	This research concentrates on the Steiner Minimal Tree problem,
	henceforth referred to as the SMT problem.  We present several
	algorithms for calculating Steiner Minimal Trees, including the
	first parallel algorithm for doing so.  Several implementation
	issues are discussed, some new results are presented, and
	several ideas for future work are proposed.

	In Chapter II we review the first fundamental algorithm for
	calculating SMT's and we present a simple, effective heuristic
	which achieves some quite remarkable results.  In Chapter III
	problem decomposition for SMT's is outlined, and a new parallel
	algorithm for this decomposition is proposed.  In Chapter IV we
	present and discuss the implementation of a parallel algorithm
	which serves as the basis for the solution to the entire
	problem.  In Chapter V the problem of extracting  the correct
	answer from a list of potential candidates is discussed.
	Results are presented in Chapter VI, with conclusions and
	%future work following in Chapters VII and VIII, respectively.
	future work following in Chapter VII.
