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   .  Sorted vectors
  15   .  Q-Heaps
  16
  17 *  Advanced MST Algorithms
  18
  19   o  Minor-closed classes
  20   o  Fredman-Tarjan algorithm
  21   .  MST verification
  22   .  Randomized algorithms
  23   .  ?? Chazelle ??
  24   .  ?? Pettie ??
  25
  26 *  Ranking combinatorial objects
  27
  28   o  Ranking and unranking
  29   o  Ranking of permutations
  30   o  Ranking of k-permutations
  31   o  Restricted permutations
  32   o  Hatcheck lady and other derangements
  33   .  ?? other objects ??
  34   .  ?? general perspective ??
  35
  36 *  Dynamic MST algorithms
  37
  38   .  (Semi-)dynamic algorithms
  39   .  Sleator-Tarjan trees
  40   .  ET-trees
  41   .  Fully dynamic connectivity
  42   .  Semi-dynamic MST
  43   .  Fully dynamic MST
  44
  45 TODO:
  46
  47 Spanning trees:
  48
  49 - cite Eisner's tutorial \cite{eisner:tutorial}
  50 - \cite{pettie:onlineverify} online lower bound
  51 - mention Steiner trees
  52 - mention matroids
  53 - sorted weights
  54 - mention disconnected graphs
  55 - Euclidean MST
  56 - Some algorithms (most notably Fredman-Tarjan) do not need flattening
  57 - reference to mixed Boruvka-Jarnik
  58 - use the notation for contraction by a set
  59 - practical considerations: katriel:cycle, moret:practice (mention pairing heaps)
  60 - parallel algorithms: p243-cole (are there others?)
  61
  62 Models:
  63
  64 - bit tricks: reference to HAKMEM
  65 - mention in-place radix-sorting?
  66 - consequences of Q-Heaps: Thorup's undirected SSSP etc.
  67 - refs on Cartesian trees
  68 - update notation.tex
  69 - iteration of Q-Heaps
  70
  71 Ranking:
  72
  73 - the general perspective: is it only a technical trick?
  74 - ranking of permutations on general sets, relationship with integer sorting
  75
  76 Notation:
  77
  78 - \O(...) as a set?
  79 - G has to be connected, so m=O(n)
  80 - impedance mismatch in terminology: contraction of G along e vs. contraction of e.
  81 - use \delta(X) notation
  82 - unify use of n(G) vs. n
  83 - use calligraphic letters from ams?
  84 - change the notation for contractions -- use double slash instead of the dot?