-* Minimum spanning trees
+* Minimum Spanning Trees
+ o The Problem
o Basic properties
o Red/Blue meta-algorithm
o Classical algorithms
- o Fredman-Tarjan algorithm
- o ?? Chazelle ??
- o ?? Pettie ??
- o Minor-closed classes
- o MST verification
- o Randomized algorithms
+ o Contractive algorithms
-* Integer data structures
+* Fine Details of Computation
- o Models of computation
+ o Models and machines
+ o Radix-sorting
o Bit tricks
- o Ranking sets
- o Bitwise B-trees
o Q-Heaps
+* Advanced MST Algorithms
+
+ o Minor-closed classes
+ o Fredman-Tarjan algorithm
+ . MST verification
+ . Randomized algorithms
+ . ?? Chazelle ??
+ . ?? Pettie ??
+ o Special cases and related problems
+
* Ranking combinatorial objects
- o Ranking of permutations: history
- o Linear-time algorithm
- o k-permutations
- o Permutations with no fixed point
- o ?? other 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
- o (Semi-)dynamic algorithms
- o Sleator-Tarjan trees
- o ET-trees
- o Fully dynamic connectivity
- o Semi-dynamic MST
- o Fully dynamic MST
+ . (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
+
+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
+
+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?