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   o  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   o  Ranking and unranking
  30   o  Ranking of permutations
  31   o  Ranking of k-permutations
  32   o  Restricted permutations
  33   o  Hatcheck lady and other derangements
  34   .  ?? other objects ??
  35   .  ?? general perspective ??
  36
  37 *  Dynamic MST algorithms
  38
  39   .  (Semi-)dynamic algorithms
  40   .  Sleator-Tarjan trees
  41   .  ET-trees
  42   .  Fully dynamic connectivity
  43   .  Semi-dynamic MST
  44   .  Fully dynamic MST
  45
  46 TODO:
  47
  48 Spanning trees:
  49
  50 - cite Eisner's tutorial \cite{eisner:tutorial}
  51 - \cite{pettie:onlineverify} online lower bound
  52 - mention Steiner trees
  53 - mention matroids
  54 - sorted weights
  55 - mention disconnected graphs
  56 - Euclidean MST
  57 - Some algorithms (most notably Fredman-Tarjan) do not need flattening
  58 - reference to mixed Boruvka-Jarnik
  59 - use the notation for contraction by a set
  60
  61 Models:
  62
  63 - bit tricks: reference to HAKMEM
  64 - mention in-place radix-sorting?
  65
  66 Ranking:
  67
  68 - the general perspective: is it only a technical trick?
  69 - ranking of permutations on general sets, relationship with integer sorting
  70 - mention approximation of permanent
  71 - use \pi[x...y]
  72
  73 Notation:
  74
  75 - \O(...) as a set?
  76 - G has to be connected, so m=O(n)
  77 - impedance mismatch in terminology: contraction of G along e vs. contraction of e.
  78 - use \delta(X) notation
  79 - unify use of n(G) vs. n
  80 - use calligraphic letters from ams?
  81 - change the notation for contractions -- use double slash instead of the dot?