*  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

  o  (Semi-)dynamic algorithms
  o  ET-trees
  o  Fully dynamic connectivity
  o  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:

Preface:

- mention notation
- cite GA booklet
- mention bugs in Valeria's verification paper

- G has to be connected, so m=O(n)

Spanning trees:

- cite Eisner's tutorial \cite{eisner:tutorial}

Applications:

- K best trees
- degree-restricted cases and arborescences
- bounded expansion classes?
- finding all MST's

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 vlastne za matice co splnuji 4.5.2
- JN: bounded-degree restriction graphs; would it imply general speedup?

Notation:

- use \delta(X) notation
- use the notation for contraction by a set
- unify use of n(G) vs. n
- introduce \widehat\O early

Typography:

* formatting of multi-line \algin, \algout
- use calligraphic letters from ams?

Global:

- each chapter should make clear in which model we work
- clean up bibliography

Pictures:

- structure of a Q-heap