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   .  Bit tricks
  13   .  Ranking sets
  14   .  Bitwise B-trees
  15   .  Q-Heaps
  16
  17 *  Advanced MST Algorithms
  18
  19   o  Minor-closed classes
  20   o  Fredman-Tarjan algorithm
  21   .  ?? Chazelle ??
  22   .  ?? Pettie ??
  23   .  MST verification
  24   .  Randomized algorithms
  25
  26 *  Ranking combinatorial objects
  27
  28   .  Ranking of permutations: history
  29   .  Linear-time algorithm
  30   .  k-permutations
  31   .  Permutations with no fixed point
  32   .  ?? other objects ??
  33
  34 *  Dynamic MST algorithms
  35
  36   .  (Semi-)dynamic algorithms
  37   .  Sleator-Tarjan trees
  38   .  ET-trees
  39   .  Fully dynamic connectivity
  40   .  Semi-dynamic MST
  41   .  Fully dynamic MST
  42
  43 TODO:
  44
  45 - cite Eisner's tutorial \cite{eisner:tutorial}
  46 - \cite{pettie:onlineverify} online lower bound
  47 - mention Steiner trees
  48 - mention matroids
  49 - sorted weights
  50 - mention disconnected graphs
  51 - Euclidean MST
  52 - Some algorithms (most notably Fredman-Tarjan) do not need flattening
  53
  54 Notation:
  55
  56 - \O(...) as a set?
  57 - G has to be connected, so m=O(n)
  58 - impedance mismatch in terminology: contraction of G along e vs. contraction of e.
  59 - use \delta(X) notation
  60 - unify use of n(G) vs. n