+\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.
projects / saga.git / blobdiff