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   o  Q-Heaps
  15
  16 *  Advanced MST Algorithms
  17
  18   o  Minor-closed classes
  19   o  Fredman-Tarjan algorithm
  20   .  MST verification
  21   .  Randomized algorithms
  22   .  ?? Chazelle ??
  23   .  ?? Pettie ??
  24   .  Other classes of graphs
  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 - 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 - practical considerations: katriel:cycle, moret:practice (mention pairing heaps)
  59 - parallel algorithms: p243-cole (are there others?)
  60 - mention 3-regular graphs; bounded expansion?
  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 - add more context from thorup:aczero, also mention FP operations
  68 - refs on Cartesian trees
  69 - update notation.tex
  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 - JN: explain approx scheme
  76 - JN: 4.5.1:  neslo by preci isolovat nejaky vlstnosti restriction matrices
  77   tak aby byl speedup? Staci napr predpokladat 4.5.2 (jako to postulovat)
  78   co je to vlstne za matice co splnuji 4.5.2
  79 - JN: bounded-degree restriction graphs; would it imply general speedup?
  80
  81 Notation:
  82
  83 - \O(...) as a set?
  84 - G has to be connected, so m=O(n)
  85 - impedance mismatch in terminology: contraction of G along e vs. contraction of e.
  86 - use \delta(X) notation
  87 - unify use of n(G) vs. n
  88 - use calligraphic letters from ams?
  89 - change the notation for contractions -- use double slash instead of the dot?