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   o  MST verification
  21   o  Linear-time verification
  22   .  A randomized algorithm
  23   .  ?? Chazelle ??
  24   .  ?? Pettie ??
  25   o  Special cases and related problems
  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 matroids
  53 - move the remark on disconnected graphs? separate section?
  54 - Some algorithms (most notably Fredman-Tarjan) do not need flattening
  55 - reference to mixed Boruvka-Jarnik
  56 - use the notation for contraction by a set
  57 - practical considerations: katriel:cycle, moret:practice (mention pairing heaps)
  58 - parallel algorithms: p243-cole (are there others?)
  59 - bounded expansion classes?
  60 - restricted cases and arborescences
  61 - mention parallel algorithms (see remarks in Karger)
  62 - Pettie's paper on random bits
  63
  64 Models:
  65
  66 - bit tricks: reference to HAKMEM
  67 - mention in-place radix-sorting?
  68 - consequences of Q-Heaps: Thorup's undirected SSSP etc.
  69 - add more context from thorup:aczero, also mention FP operations
  70 - expand the section on radix-sorting, mention Buchsbaum
  71
  72 Ranking:
  73
  74 - the general perspective: is it only a technical trick?
  75 - ranking of permutations on general sets, relationship with integer sorting
  76 - JN: explain approx scheme
  77 - JN: 4.5.1:  neslo by preci isolovat nejaky vlstnosti restriction matrices
  78   tak aby byl speedup? Staci napr predpokladat 4.5.2 (jako to postulovat)
  79   co je to vlstne za matice co splnuji 4.5.2
  80 - JN: bounded-degree restriction graphs; would it imply general speedup?
  81
  82 Notation:
  83
  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?
  90 - introduce \widehat\O early
  91
  92 Varia:
  93
  94 - cite GA booklet