PLAN

   1 *  Minimum Spanning Trees
   2
   3   o  The Problem
   4   o  Basic properties
   5   o  Red/Blue meta-algorithm
   6   o  Classical algorithms
   7   o  Contractive algorithms
   8
   9 *  Fine Details of Computation
  10
  11   o  Models and machines
  12   o  Radix-sorting
  13   .  Bit tricks
  14   .  Ranking sets
  15   .  Bitwise B-trees
  16   .  Q-Heaps
  17
  18 *  Advanced MST Algorithms
  19
  20   o  Minor-closed classes
  21   o  Fredman-Tarjan algorithm
  22   .  ?? Chazelle ??
  23   .  ?? Pettie ??
  24   .  MST verification
  25   .  Randomized algorithms
  26
  27 *  Ranking combinatorial objects
  28
  29   .  Ranking of permutations: history
  30   .  Linear-time algorithm
  31   .  k-permutations
  32   .  Permutations with no fixed point
  33   .  ?? other objects ??
  34
  35 *  Dynamic MST algorithms
  36
  37   .  (Semi-)dynamic algorithms
  38   .  Sleator-Tarjan trees
  39   .  ET-trees
  40   .  Fully dynamic connectivity
  41   .  Semi-dynamic MST
  42   .  Fully dynamic MST
  43
  44 TODO:
  45
  46 - fix proof of the local contraction alg
  47 - cite Eisner's tutorial \cite{eisner:tutorial}
  48 - \cite{pettie:onlineverify} online lower bound
  49 - mention Steiner trees
  50 - mention matroids
  51 - sorted weights
  52 - mention disconnected graphs
  53 - Euclidean MST
  54 - Some algorithms (most notably Fredman-Tarjan) do not need flattening
  55 - mention in-place radix-sorting?
  56 - ranking of permutations on general sets, relationship with integer sorting
  57 - reference to mixed Boruvka-Jarnik
  58 - bit tricks: reference to HAKMEM
  59
  60 Notation:
  61
  62 - \O(...) as a set?
  63 - G has to be connected, so m=O(n)
  64 - impedance mismatch in terminology: contraction of G along e vs. contraction of e.
  65 - use \delta(X) notation
  66 - unify use of n(G) vs. n