\newpage
\section{Further Parallelization}

	There remains a great deal of work that can be done on the
	Steiner Minimal Tree problem in the parallel arena.  The first
	thing to consider is whether there are other ways to approach the
	parallel generation of T\_list that would be more efficient.
	Improvement in this area would push the computation pendulum
	even further away from T\_list generation and towards
	SMT extraction.

	The next thing to consider is the entire extraction
	process.  The initial generation of the {\it incompatibility
	matrix} has the appearance of easy parallelization.  The forest
	management technique introduced by Cockayne and Hewgill could
	also be put into a parallel framework, thereby speeding up the
	preparation for extraction quite a bit.

	With this initialization out of the way, decomposition could then
	be considered.  The best possible enhancement here might
	be the addition of thresholds.  As with most parallel
	algorithms, for any problem smaller than a particular size it
	is usually faster to solve it sequentially.
	These thresholds could come into play in determining
	whether to call a further decomposition, such as the cycle
	decomposition introduced by Cockayne and Hewgill that was
	discussed in Chapter V.

	The final option for parallelization is one that may yield the
	best results, and that is in the extraction itself.  Extraction
	is basically a branch and bound process, using the {\it
	incompatibility matrix}.  This branch and bound is primed with
	the length of the MST as the initial bound, and continues until
	all possible combinations have been considered.  The easiest
	implementation here would probably be the idea presented in the
	paper by Quinn and Deo~\cite{qd85:ubspbbbba} that served as the
	basis for the parallel algorithm in Chapter IV.

\vspace*{11pt}
\section{Additional Problems}

	\vspace*{11pt}
	\subsection{1-Reliable Steiner Tree Problem}

	If we would like to be able to sustain a single failure of any
	vertex, without interrupting communication among remaining
	vertices, the minimum length network problem takes on a
	decidedly different structure.  For example, in any FST
	all of the original vertices are of degree 1, and hence any one
	can be disconnected from the network by a single failure of the
	adjacent Steiner Point.

        We would clearly like a minimum length 2-connected network.
        The answer can be the minimum length Hamiltonian cycle
        (consider the vertices of the unit square), but it need not be,
        as shown in the $\Theta$ graph given in Figure~\ref{fig:Theta}.

	Here we can add  Steiner points near the vertices of degree 3,
	and reduce the network length without sacrificing 2-connectivity.
	This is not just a single graph, but is a member of a family of
	graphs that look like ladders, where the $\Theta$ graph has
	only one internal rung.  We hope to extend earlier work
	providing constructions on 2-connected graphs~\cite{hedet} to
	allow effective application of an Annealing Algorithm that
	could walk through graphs within the 2-connected class.

        \begin{figure}[h]
	\vspace*{22pt}
        \centerline{\psfig{figure=chap08/theta1.ps,height=3.0in}}
               \caption{Theta graph.}
               \label{fig:Theta}
	\vspace*{22pt}
        \end{figure}

	\vspace*{11pt}
	\subsection{Addition to Existing Networks}

	Cockayne has presented the following problem:  Given a
	connected graph $G$ and a set of vertices, $V$,  which are not
	on edges of $G$, find a connected graph $H$ which has $G$ as a
	subgraph and contains the vertices in $V$.  

	This problem is very interesting when you consider it in the
	context of a growing road network.  In this case you have a
	small town with an existing road network and a few new houses
	and businesses that have been built outside of the town.  Your
	job is to construct a set of roads with minimum length that
	connects these new houses and businesses to the town's road
	network.

	The Steiner Minimal Tree problem we have discussed here can be
	seen as a special case of this new problem.  For the SMT, the
	existing graph is empty, and all new vertices must be
	connected with minimal length.  Therefore it is quite simple to
	deduce that this is also an NP-Complete problem.
