
\section{Conclusions}

	This work is a synthesis of several new results. In Chapter II
	we presented a new heuristic for the SMT problem as well as a
	new measure of accuracy for heuristics.  The heuristic was
	based upon Simulated Annealing and was an outgrowth of the
	1-Steiner problem.  The measure of accuracy expresses how much
	of the distance from the MST to the SMT a heuristic covers
	on a particular problem.  This measure showed that our
	heuristic has achieved a score of over $95\%$ on every randomly
	generated 100 point problem we tested, while using less than
	$\frac{1}{10}$th the cpu time currently used to solve the
	problem exactly.

	In Chapter III we presented a new parallel algorithm for
	calculating the Steiner Hull and thereby decomposing the
	problem.  This algorithm while not having a great theoretical
	speedup, in practice, computes the Steiner Hull for randomly
	generated 100 point problems rapidly.

	The foundation of this thesis, presented in Chapters IV and
	VI, is a parallel algorithm for the generation of
	T\_list and its implementation.  When Winter developed his
	algorithm, the time for extraction dominated the overall
	computation time.  After Cockayne and Hewgill's work, the time
	to generate T\_list dominated the overall computation time.
	The parallel algorithms we presented in Chapters III and IV
	were implemented in a program called PARSTEINER94, and the
	results presented in Chapter IV show that the time to generate
	T\_list has now been cut so much that the
	extraction time once again dominates the overall computation
	time.

	In Chapter IV we also presented a characterization of SMT's for
	certain sizes of grids.  The characterization of the SMT for a
	2 x m grid has been studied in depth, and is well defined.  The
	only other characterization for grids previously known were for
	square grids.  In this work we present the characterizations of
	SMT's for 2 x m grids, as well as conjectured characterizations
	of SMT's for 3 x m, and 4 x m grids.
