*  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
  o  Bit tricks
  .  Sorted vectors
  .  Q-Heaps

*  Advanced MST Algorithms

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

*  Ranking combinatorial objects

  o  Ranking and unranking
  o  Ranking of permutations
  o  Ranking of k-permutations
  o  Restricted permutations
  o  Hatcheck lady and other derangements
  .  ?? other objects ??
  .  ?? general perspective ??

*  Dynamic MST algorithms

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

TODO:

Spanning trees:

- cite Eisner's tutorial \cite{eisner:tutorial}
- \cite{pettie:onlineverify} online lower bound
- mention Steiner trees
- mention matroids
- mention disconnected graphs
- Euclidean MST
- Some algorithms (most notably Fredman-Tarjan) do not need flattening
- reference to mixed Boruvka-Jarnik
- use the notation for contraction by a set
- practical considerations: katriel:cycle, moret:practice (mention pairing heaps)
- parallel algorithms: p243-cole (are there others?)

Models:

- bit tricks: reference to HAKMEM
- mention in-place radix-sorting?
- consequences of Q-Heaps: Thorup's undirected SSSP etc.
- add more context from thorup:aczero, also mention FP operations
- refs on Cartesian trees
- update notation.tex

Ranking:

- the general perspective: is it only a technical trick?
- 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
- use calligraphic letters from ams?
- change the notation for contractions -- use double slash instead of the dot?