*  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
  o  Q-Heaps

*  Advanced MST Algorithms

  o  Minor-closed classes
  o  Fredman-Tarjan algorithm
  o  MST verification
  o  Linear-time verification
  .  A randomized algorithm
  .  ?? Chazelle ??
  .  ?? Pettie ??
  o  Special cases and related problems

*  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 matroids
- mention disconnected graphs
- 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?)
- bounded expansion classes?
- restricted cases and arborescences
- mention randomized algorithms (see remarks in Karger)

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
- expand the section on radix-sorting, mention Buchsbaum

Ranking:

- the general perspective: is it only a technical trick?
- ranking of permutations on general sets, relationship with integer sorting
- JN: explain approx scheme
- JN: 4.5.1:  neslo by preci isolovat nejaky vlstnosti restriction matrices
  tak aby byl speedup? Staci napr predpokladat 4.5.2 (jako to postulovat)
  co je to vlstne za matice co splnuji 4.5.2
- JN: bounded-degree restriction graphs; would it imply general speedup?

Notation:

- 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?
- introduce \widehat\O early

Varia:

- cite GA booklet