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   o  (Semi-)dynamic algorithms
  35   o  ET-trees
  36   o  Fully dynamic connectivity
  37   o  Dynamic MST
  38
  39 *  Ranking Combinatorial Objects
  40
  41   o  Ranking and unranking
  42   o  Ranking of permutations
  43   o  Ranking of k-permutations
  44   o  Restricted permutations
  45   o  Hatcheck lady and other derangements
  46   .  ?? other objects ??
  47   .  ?? general perspective ??
  48
  49 TODO:
  50
  51 Spanning trees:
  52
  53 - cite Eisner's tutorial \cite{eisner:tutorial}
  54 - \cite{pettie:onlineverify} online lower bound
  55 - move the remark on disconnected graphs? separate section?
  56 - mention graphs with non-unique weights? also in the separate section?
  57 - Some algorithms (most notably Fredman-Tarjan) do not need flattening
  58 - citation of mixed Boruvka-Jarnik
  59 - use the notation for contraction by a set
  60 - mention bugs in Valeria's verification paper
  61 - more references on decision trees
  62 - rename theorem on Minimality by order
  63 - introduce Cut rule and Cycle rule earlier
  64 - Lemma: deletion of a non-MST edge does not alter the MST
  65
  66 Related:
  67 - practical considerations: katriel:cycle, moret:practice (mention pairing heaps)
  68 - parallel algorithms: p243-cole (see also remarks in Karger and pettie:minirand), pettie:parallel
  69 - K best trees
  70 - random sampling (propp:randommst)
  71 - degree-restricted cases and arborescences
  72 - bounded expansion classes?
  73 - mention matroids
  74
  75 Models:
  76
  77 - bit tricks: reference to HAKMEM
  78 - mention in-place radix-sorting?
  79 - consequences of Q-Heaps: Thorup's undirected SSSP etc.
  80 - add more context from thorup:aczero, also mention FP operations
  81 - Tarjan79 is mentioned by Pettie to define Pointer machines
  82 - add references to the C language
  83 - PM: unify yardsticks
  84 - all data structures should mention space complexity
  85
  86 Dynamic:
  87
  88 - What is the origin of the semidynamic MSF?
  89 - lower bounds
  90
  91 Ranking:
  92
  93 - the general perspective: is it only a technical trick?
  94 - ranking of permutations on general sets, relationship with integer sorting
  95 - JN: explain approx scheme
  96 - JN: 4.5.1:  neslo by preci isolovat nejaky vlstnosti restriction matrices
  97   tak aby byl speedup? Staci napr predpokladat 4.5.2 (jako to postulovat)
  98   co je to vlstne za matice co splnuji 4.5.2
  99 - JN: bounded-degree restriction graphs; would it imply general speedup?
 100
 101 Notation:
 102
 103 - G has to be connected, so m=O(n)
 104 - impedance mismatch in terminology: contraction of G along e vs. contraction of e.
 105 - use \delta(X) notation
 106 - unify use of n(G) vs. n
 107 - use calligraphic letters from ams?
 108 - change the notation for contractions -- use double slash instead of the dot?
 109 - introduce \widehat\O early
 110 - unify { x ; ... }, { x | ...} and { x : ... }
 111 - capitalize Pointer Machine
 112 - Ackermann: which of the Tarjan's set union papers should we cite?
 113 - Ackermann function vs. Ackermann's function
 114
 115 Varia:
 116
 117 - cite GA booklet
 118 - minimize the use of Remarks, use \paran instead
 119 - formatting of multi-line \algin, \algout