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   .  Almost minimum trees
  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 Applications:
  53
  54 - K best trees
  55 - degree-restricted cases and arborescences
  56 - bounded expansion classes?
  57 - finding all MST's
  58
  59 Ranking:
  60
  61 - the general perspective: is it only a technical trick?
  62 - ranking of permutations on general sets, relationship with integer sorting
  63 - JN: explain approx scheme
  64 - JN: 4.5.1:  neslo by preci isolovat nejaky vlstnosti restriction matrices
  65   tak aby byl speedup? Staci napr predpokladat 4.5.2 (jako to postulovat)
  66   co je to vlastne za matice co splnuji 4.5.2
  67 - JN: bounded-degree restriction graphs; would it imply general speedup?
  68
  69 Notation:
  70
  71 - use \delta(X) notation
  72 - use the notation for contraction by a set
  73 - unify use of n(G) vs. n
  74 - introduce \widehat\O early
  75
  76 Typography:
  77
  78 * formatting of multi-line \algin, \algout
  79 - use calligraphic letters from ams?
  80
  81 Global:
  82
  83 - each chapter should make clear in which model we work
  84 - clean up bibliography