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