\documentstyle[12pt]{article}
\textwidth=6.0in
\textheight=9.25in
\evensidemargin=0.25in
\oddsidemargin=0.25in
\topmargin=-0.75in
%\topskip=0pt
\baselineskip=12pt
\parskip=0pt
\parindent=0em
\input psfig
\begin{document}
%\pagenumbering{roman}
\title{Parallel Computation of Steiner Minimal Trees}
\author{ Frederick C. Harris, Jr.}
\date{\quad}
\maketitle

\addcontentsline{toc}{section}{Abstract}
%\parskip=4pt
\begin{abstract}
	Given a set of  $N$ cities, construct a connected network which
	has minimum length.  The problem is simple enough, but the
	catch is that you are allowed to add junctions in your
	network.  Therefore the problem becomes how many extra
	junctions should be added, and where should they be placed so
	as to minimize the overall network length.

        This intriguing optimization problem is known as the
        Steiner Minimal Tree Problem, where the junctions that are
        added to the network are called Steiner Points.  

	The foundation of this presentation is a parallel algorithm for
	the generation of what Pawel Winter termed T\_list and its
	implementation.  This generation of T\_list is followed by the
	extraction of the proper answer.  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 implemented were implemented in a
	program called PARSTEINER94, and the results show that the time
	to generate T\_list has now been cut by an order of
	magnitude.   So now the extraction time once again dominates
	the overall computation time.

	We also present a characterization of SMT's for certain sizes
	of grids.  The characterization of the SMT for a 2 x m grid was
	generally known. The only other characterization for grids
	previously known were for square grids.  In this work we
	present the characterization of SMT's for 2 x m grids,
	as well as a characterization of SMT's for 3 x m, and 4 x m
	grids.

\end{abstract}

%Committee: S.T. Hedetniemi (chair), R.C. Laskar, B.A. Malloy, R.P.  Pargas

\end{document}
