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   o  A randomized algorithm
  23   o  Special cases and related problems
  24
  25 *  Approaching Optimality
  26
  27   o  Soft heaps
  28   o  Robust contractions
  29   o  Decision trees
  30   o  An optimal algorithm
  31
  32 *  Dynamic MST algorithms
  33
  34   .  (Semi-)dynamic algorithms
  35   .  Sleator-Tarjan trees and semi-dynamic MST
  36   .  ET-trees
  37   .  Fully dynamic connectivity
  38   .  Dynamic MST
  39
  40 *  Ranking Combinatorial Objects
  41
  42   o  Ranking and unranking
  43   o  Ranking of permutations
  44   o  Ranking of k-permutations
  45   o  Restricted permutations
  46   o  Hatcheck lady and other derangements
  47   .  ?? other objects ??
  48   .  ?? general perspective ??
  49
  50 TODO:
  51
  52 Spanning trees:
  53
  54 - cite Eisner's tutorial \cite{eisner:tutorial}
  55 - \cite{pettie:onlineverify} online lower bound
  56 - mention matroids
  57 - move the remark on disconnected graphs? separate section?
  58 - Some algorithms (most notably Fredman-Tarjan) do not need flattening
  59 - reference to mixed Boruvka-Jarnik
  60 - use the notation for contraction by a set
  61 - practical considerations: katriel:cycle, moret:practice (mention pairing heaps)
  62 - parallel algorithms: p243-cole (see also remarks in Karger and pettie:minirand), pettie:parallel
  63 - bounded expansion classes?
  64 - degree-restricted cases and arborescences
  65 - random sampling (propp:randommst)
  66 - mention bugs in Valeria's verification paper
  67 - more references on decision trees
  68
  69 Models:
  70
  71 - bit tricks: reference to HAKMEM
  72 - mention in-place radix-sorting?
  73 - consequences of Q-Heaps: Thorup's undirected SSSP etc.
  74 - add more context from thorup:aczero, also mention FP operations
  75 - Tarjan79 is claimed by Pettie to define Pointer machines
  76 - add references to the C language
  77 - PM: unify yardsticks
  78
  79 Ranking:
  80
  81 - the general perspective: is it only a technical trick?
  82 - ranking of permutations on general sets, relationship with integer sorting
  83 - JN: explain approx scheme
  84 - JN: 4.5.1:  neslo by preci isolovat nejaky vlstnosti restriction matrices
  85   tak aby byl speedup? Staci napr predpokladat 4.5.2 (jako to postulovat)
  86   co je to vlstne za matice co splnuji 4.5.2
  87 - JN: bounded-degree restriction graphs; would it imply general speedup?
  88
  89 Notation:
  90
  91 - G has to be connected, so m=O(n)
  92 - impedance mismatch in terminology: contraction of G along e vs. contraction of e.
  93 - use \delta(X) notation
  94 - unify use of n(G) vs. n
  95 - use calligraphic letters from ams?
  96 - change the notation for contractions -- use double slash instead of the dot?
  97 - introduce \widehat\O early
  98 - unify { x ; ... }, { x | ...} and { x : ... }
  99 - capitalize Pointer Machine
 100 - define \alpha(m,n) and use it instead of \alpha(n)
 101
 102 Varia:
 103
 104 - cite GA booklet
 105 - minimize the use of Remarks, use \paran instead