*  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
  o  Almost minimum trees

*  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

TODO:

Applications:

- degree-restricted cases and arborescences
- bounded expansion classes?

Ranking:

- ranking of permutations on general sets, relationship with integer sorting
- 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?

Typography:

- formatting of multi-line \algin, \algout