*  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
  o  A randomized algorithm
  o  Special cases and related problems

*  Approaching Optimality

  o  Soft heaps
  o  Robust contractions
  o  Decision trees
  o  An optimal algorithm

*  Dynamic MST algorithms

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

*  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 ??

TODO:

Spanning trees:

- cite Eisner's tutorial \cite{eisner:tutorial}
- \cite{pettie:onlineverify} online lower bound
- mention matroids
- move the remark on disconnected graphs? separate section?
- 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 (see also remarks in Karger and pettie:minirand), pettie:parallel
- bounded expansion classes?
- degree-restricted cases and arborescences
- random sampling (propp:randommst)
- mention bugs in Valeria's verification paper
- more references on decision trees

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
- Tarjan79 is claimed by Pettie to define Pointer machines
- add references to the C language
- PM: unify yardsticks

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
- unify { x ; ... }, { x | ...} and { x : ... }
- capitalize Pointer Machine
- define \alpha(m,n) and use it instead of \alpha(n)

Varia:

- cite GA booklet
- minimize the use of Remarks, use \paran instead