
\section{Introduction and Overview}

	Once the T\_list discussed in Chapter IV is formed, the next
	step is to extract the proper answer from it.  Winter described
	this in step 7 of his algorithm (Figure \ref{fig:winter.alg}).
	His description stated that unions of FST's saved in T\_list
	were to be formed subject to constraints described in his
	paper.  The shortest union is the SMT for the original points.

	The constraints he described were quite obvious considering the
	definition of an SMT.  First, the answer had to cover all the
	original points.  Second, the union of FST's could not contain a
	cycle.  Third, the answer is bounded in length by the length of
	the MST.

	This led Winter to implement a simple exhaustive search
	algorithm over the FST's in T\_list.  This approach yields a
	sample space  of size ${\cal O}(2^{m})$ (where m is the number
	of trees in T\_list) that has to be searched.  This
	exponentiality is born out in his work where he stated that for
	problems with more than 15 points ``the computation time needed
	to form the union of FST's dominates the computation time
	needed for the construction of the
	FST's~\cite{winter85:aaftspitep}.''  An example of the input the
	last step of Winter's algorithm receives (T\_list) is given in
	Figure~\ref{fig:t_list}.  The answer it extracts (the SMT) is
	shown in Figure~\ref{fig:SMT}.

	\begin{figure} 
	\vspace*{22pt}
	\centerline{\psfig{figure=chap05/tree.1.before.ps,height=6.0in}}
	\caption{\label{fig:t_list}T\_list for a random set of points.}
	\vspace*{22pt} 
	\end{figure}

        \begin{figure}
        \vspace*{22pt}
        \centerline{\psfig{figure=chap05/tree.1.ps,height=6.0in}}
        \caption{\label{fig:SMT}SMT extracted from T\_list for a random set of points.}
        \vspace*{22pt}
        \end{figure}

        \vspace*{11pt}
\section{Incompatibility Matrix}

\textheight=10in
	Although the SMT problem attracted many people through the
	early 70's the lack of results seemed to dampen most of their
	spirits.  It wasn't until Winter's algorithm was published that
	the research community received the spark it needed to work on
	the SMT problem with renewed vigor.  With the insight Winter
	provided into the problem, an attempt to computerize the
	solution of the SMT problem began anew.

	Enhancement of this algorithm was first attempted by Cockayne
	and Hewgill at the University of Victoria.  For this
	implementation Cockayne and Hewgill spent most of their work on
	the back end of the problem, or the extraction from T\_list,
	and used Winter's algorithm to generate T\_list.  This work on
	the extraction focused on what they termed an {\it
	incompatibility matrix}.  This matrix had one row and
	one column for each member of T\_list.  The entries in this
	matrix were flags corresponding to one of three possibilities:
	{\it compatible}, {\it incompatible}, or {\it don't know}.  The
	rationale behind the construction of this matrix is the fact
	that it is faster to look up the value in a matrix than it is
	to check for the creation of cycles and improper angles during
	the union of FST's.

	The first value calculations for this matrix were
	straightforward.  If two trees do not have any points in common
	then we {\it don't know} if they are incompatible or not.  If
	they have two or more points in common then they form a cycle
	and are {\it incompatible}.  If they have only one point in
	common and the angle at the intersection point is less than
	$120^{\circ}$ then they are also {\it incompatible}. In all
	other cases they are {\it compatible}.

	This simple enhancement to the extraction process enabled
	Cockayne and Hewgill to solve all randomly generated problems
	of size up to 17 vertices in a little over three
	minutes~\cite{ch86:ecosmtitp}.

        \vspace*{11pt}
\section{Decomposition}
	
	The next focus of Cockayne and Hewgill's work was in the area
	of the decomposition of the problem.  As was discussed earlier in
	Chapter III, the best theorems for any problem, especially
	non-polynomial problems, are those of the form ``If property
	${\cal P}$ exists then the problem can be decomposed.''  Since
	the formation of unions of FST's is exponential in nature any
	theorem of this type is important.

	Cockayne and Hewgill's theorem states:  ``Let $A_{1}$ and $A_{2}$
	be subsets of $A$ satisfying (i) $A_{1}\bigcup A_{2} = A$
	(ii) $|A_{1} \bigcap A_{2}| = 1$ and (iii) the leaf set of each
	FST in T\_list is entirely contained in $A_{1}$ or $A_{2}$.
	Then any SMT on $A$ is the union of separate SMT's on $A_{1}$
	and $A_{2}$~\cite{ch86:ecosmtitp}.''  This means that if you
	break T\_list into biconnected components, the SMT will be the
	union of the SMT's on those components.

	Their next decomposition theorem allowed further improvements in
	the calculation of SMT's.  This theorem stated that if you had a
	component of T\_list left from the previous theorem
	and if the T\_list members of that component form a cycle, then
	it might be possible to break that cycle and apply the previous
	algorithm again.  The cycle could be broken if there existed a
	vertex $v$ whose removal would change that component from one
	biconnected component to more than one.
\newpage
\textheight=9in
	With these two decomposition theorems, Cockayne and Hewgill
	were able to calculate the SMT for 79 of 100 randomly generated
	30 point problems.  The remaining 21 would not decompose into
	blocks of size 17 or smaller, and thus would have taken too
	much computation time~\cite{ch86:ecosmtitp}.  This calculation
	was implemented in the program they called EDSTEINER86.

        \vspace*{11pt}
\section{Forest Management}

	Their next work, which was implemented in a program called
	EDSTEINER89, focused on improvements to the {\it incompatibility
	matrix} previously described.  Their goal was to reduce the
	number of {\it don't know}'s in the matrix and possibly remove some
	FST's from T\_list altogether.

	They proposed two refinements for calculating the entry into
	the {\it incompatibility matrix} and one Tree Deletion
	Theorem.  The Tree Deletion Theorem stated that if there exists
	an FST in T\_list that is incompatible with all FST's
	containing a certain point $a$ then the original FST can be
	deleted since at least one FST containing $a$ will be in the
	SMT.

	This simple change allowed Cockayne and Hewgill to calculate
	the SMT for 77 of 100 randomly generated 100 point
	problems~\cite{ch92:icopsmt}. The other 23 problems could not be
	calculated in less than 12 hours and were therefore
	terminated.  For those that did complete, the computation time
	to generate T\_list had become the dominate factor in the
	overall computation time.  

	So the pendulum had swung back from the extraction of the
	correct answer from T\_list to the generation of T\_list
	dominating the computation time.  In Chapter VI we will look at
	the results of the parallel algorithm presented in Chapter IV
	to see if the pendulum can be pushed back the other way one
	more time.

