epilog.tex

   1 \ifx\endpart\undefined
   2 \input macros.tex
   3 \fi
   4
   5 \chapter{Epilogue}
   6
   7 We have seen the many facets of the minimum spanning tree problem. It has
   8 turned out that while the major question of the existence of a~linear-time
   9 MST algorithm is still open, backing off a~little bit in an~almost arbitrary
  10 direction leads to a~linear solution. This includes classes of graphs with edge
  11 density at least $\lambda_k(n)$ for an~arbitrary fixed~$k$,
  12 minor-closed classes, and graphs whose edge weights are
  13 integers. Using randomness also helps, as does having the edges pre-sorted.
  14
  15 If we do not know anything about the structure of the graph and we are only allowed
  16 to compare the edge weights, we can use the Pettie's MST algorithm.
  17 Its time complexity is guaranteed to be asymptotically optimal,
  18 but we do not know what it really is --- the best what we have is
  19 an~$\O(m\timesalpha(m,n))$ upper bound and the trivial $\Omega(m)$ lower bound.
  20
  21 One thing we however know for sure. The algorithm runs on the weakest of our
  22 computational models ---the Pointer Machine--- and its complexity is linear
  23 in the minimum number of comparisons needed to decide the problem. We therefore
  24 need not worry about the details of computational models, which have contributed
  25 so much to the linear-time algorithms for our special cases. Instead, it is sufficient
  26 to study the complexity of MST decision trees. However, aside from the properties
  27 mentioned in Section \ref{dtsect}, not much is known about these trees so far.
  28
  29 As for the dynamic algorithms, we have an~algorithm which maintains the minimum
  30 spanning forest within poly-logarithmic time per operation.
  31 The optimum complexity is once again undecided --- the known lower bounds are very far
  32 from the upper ones.
  33 The known algorithms run on the Pointer machine and we do not know if using a~stronger
  34 model can help.
  35
  36 For the ranking problems, the situation is completely different. We have shown
  37 linear-time algorithms for three important problems of this kind. The techniques,
  38 which we have used, seem to be applicable to other ranking problems. On the other
  39 hand, ranking of general restricted permutations has turned out to balance on the
  40 verge of $\#{\rm P}$-completeness. All our algorithms run
  41 on the RAM model, which seems to be the only sensible choice for problems of
  42 inherently arithmetic nature. While the unit-cost assumption on arithmetic operations
  43 is not universally accepted, our results imply that the complexity of our algorithm
  44 is dominated by the necessary arithmetics.
  45
  46 Aside from the concrete problems we have solved, we have also built several algorithmic
  47 techniques of general interest: the unification procedures using pointer-based
  48 bucket sorting (Section \ref{bucketsort}) and the vector computations on the RAM
  49 (Section \ref{bitsect}). We hope that they will be useful in many other algorithms.
  50
  51 \endpart