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