*  Minimum Spanning Trees

  o  The Problem
  o  Basic properties
  o  Red/Blue meta-algorithm
  o  Classical algorithms
  o  Contractive algorithms

*  Fine Details of Computation

  o  Models and machines
  o  Radix-sorting
  .  Bit tricks
  .  Ranking sets
  .  Bitwise B-trees
  .  Q-Heaps

*  Advanced MST Algorithms

  o  Minor-closed classes
  o  Fredman-Tarjan algorithm
  .  ?? Chazelle ??
  .  ?? Pettie ??
  .  MST verification
  .  Randomized algorithms

*  Ranking combinatorial objects

  .  Ranking of permutations: history
  .  Linear-time algorithm
  .  k-permutations
  .  Permutations with no fixed point
  .  ?? other objects ??

*  Dynamic MST algorithms

  .  (Semi-)dynamic algorithms
  .  Sleator-Tarjan trees
  .  ET-trees
  .  Fully dynamic connectivity
  .  Semi-dynamic MST
  .  Fully dynamic MST

TODO:

Spanning trees:

- prove the density bound
- fix proof of the local contraction alg
- cite Eisner's tutorial \cite{eisner:tutorial}
- \cite{pettie:onlineverify} online lower bound
- mention Steiner trees
- mention matroids
- sorted weights
- mention disconnected graphs
- Euclidean MST
- Some algorithms (most notably Fredman-Tarjan) do not need flattening
- reference to mixed Boruvka-Jarnik

Models:

- bit tricks: reference to HAKMEM
- mention in-place radix-sorting?

Ranking:

- the general perspective: is it only a technical trick?
- move description of the ranking set to the chapter on models?
- ranking of permutations on general sets, relationship with integer sorting

Notation:

- \O(...) as a set?
- G has to be connected, so m=O(n)
- impedance mismatch in terminology: contraction of G along e vs. contraction of e.
- use \delta(X) notation
- unify use of n(G) vs. n