\ifx\endpart\undefined
\input macros.tex
\fi

\chapter{Epilogue}

We have seen the many facets of the minimum spanning tree problem. It has
turned out that while the major question of the existence of a~linear-time
MST algorithm is still open, backing off a~little bit in an~almost arbitrary
direction leads to a~linear solution. This includes classes of graphs with edge
density at least $\lambda_k(n)$ for an~arbitrary fixed~$k$,
minor-closed classes, and graphs whose edge weights are
integers. Using randomness also helps, as does having the edges pre-sorted.

If we do not know anything about the structure of the graph and we are only allowed
to compare the edge weights, we can use the Pettie's MST algorithm.
Its time complexity is guaranteed to be asymptotically optimal,
but we do not know what it really is --- the best what we have is
an~$\O(m\timesalpha(m,n))$ upper bound and the trivial $\Omega(m)$ lower bound.

One thing we however know for sure. The algorithm runs on the weakest of our
computational models ---the Pointer Machine--- and its complexity is linear
in the minimum number of comparisons needed to decide the problem. We therefore
need not worry about the details of computational models, which have contributed
so much to the linear-time algorithms for our special cases. Instead, it is sufficient
to study the complexity of MST decision trees. However, aside from the properties
mentioned in Section \ref{dtsect}, not much is known about these trees so far.

As for the dynamic algorithms, we have an~algorithm which maintains the minimum
spanning forest within poly-logarithmic time per operation.
The optimum complexity is once again undecided --- the known lower bounds are very far
from the upper ones.
The known algorithms run on the Pointer machine and we do not know if using a~stronger
model can help.

For the ranking problems, the situation is completely different. We have shown
linear-time algorithms for three important problems of this kind. The techniques,
which we have used, seem to be applicable to other ranking problems. On the other
hand, ranking of general restricted permutations has turned out to balance on the
verge of $\#{\rm P}$-completeness. All our algorithms run
on the RAM model, which seems to be the only sensible choice for problems of
inherently arithmetic nature. While the unit-cost assumption on arithmetic operations
is not universally accepted, our results imply that the complexity of our algorithm
is dominated by the necessary arithmetics.

Aside from the concrete problems we have solved, we have also built several algorithmic
techniques of general interest: the unification procedures using pointer-based
bucket sorting (Section \ref{bucketsort}) and the vector computations on the RAM
(Section \ref{bitsect}). We hope that they will be useful in many other algorithms.

\endpart
