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 Spanning trees:
  47
  48 - cite Eisner's tutorial \cite{eisner:tutorial}
  49 - \cite{pettie:onlineverify} online lower bound
  50 - mention Steiner trees
  51 - mention matroids
  52 - sorted weights
  53 - mention disconnected graphs
  54 - Euclidean MST
  55 - Some algorithms (most notably Fredman-Tarjan) do not need flattening
  56 - reference to mixed Boruvka-Jarnik
  57 - use the notation for contraction by a set
  58
  59 Models:
  60
  61 - bit tricks: reference to HAKMEM
  62 - mention in-place radix-sorting?
  63
  64 Ranking:
  65
  66 - the general perspective: is it only a technical trick?
  67 - move description of the ranking set to the chapter on models?
  68 - ranking of permutations on general sets, relationship with integer sorting
  69
  70 Notation:
  71
  72 - \O(...) as a set?
  73 - G has to be connected, so m=O(n)
  74 - impedance mismatch in terminology: contraction of G along e vs. contraction of e.
  75 - use \delta(X) notation
  76 - unify use of n(G) vs. n