o Models and machines
o Radix-sorting
- . Bit tricks
- . Ranking sets
- . Bitwise B-trees
- . Q-Heaps
+ o Bit tricks
+ o Q-Heaps
* Advanced MST Algorithms
o Minor-closed classes
o Fredman-Tarjan algorithm
- . ?? Chazelle ??
- . ?? Pettie ??
- . MST verification
- . Randomized algorithms
+ o MST verification
+ o Linear-time verification
+ o A randomized algorithm
+ o Special cases and related problems
-* Ranking combinatorial objects
+* Approaching Optimality
- . Ranking of permutations: history
- . Linear-time algorithm
- . k-permutations
- . Permutations with no fixed point
- . ?? other objects ??
+ o Soft heaps
+ o Robust contractions
+ o Decision trees
+ o An optimal algorithm
* Dynamic MST algorithms
- . (Semi-)dynamic algorithms
- . Sleator-Tarjan trees
- . ET-trees
- . Fully dynamic connectivity
- . Semi-dynamic MST
- . Fully dynamic MST
+ 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:
-- cite Eisner's tutorial \cite{eisner:tutorial}
-- \cite{pettie:onlineverify} online lower bound
-- mention Steiner trees
-- mention matroids
-- sorted weights
-- mention disconnected graphs
-- Euclidean MST
-- Some algorithms (most notably Fredman-Tarjan) do not need flattening
-- mention in-place radix-sorting?
+Applications:
+
+- degree-restricted cases and arborescences
+- bounded expansion classes?
+
+Ranking:
+
+- the general perspective: is it only a technical trick?
- ranking of permutations on general sets, relationship with integer sorting
-- reference to mixed Boruvka-Jarnik
-- bit tricks: reference to HAKMEM
+- 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?
+
+Typography:
+
+* formatting of multi-line \algin, \algout
-Notation:
+Global:
-- \O(...) as a set?
-- 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
+- each chapter should make clear in which model we work
+- clean up bibliography
+- intro: \log is binary