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
+ . ?? Chazelle ??
+ . ?? Pettie ??
+ o Special cases and related problems
* Ranking combinatorial objects
- . Ranking of permutations: history
- . Linear-time algorithm
- . k-permutations
- . Permutations with no fixed point
+ 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
TODO:
+Spanning trees:
+
- 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?
-- ranking of permutations on general sets, relationship with integer sorting
- 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:
-- \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
+- use calligraphic letters from ams?
+- change the notation for contractions -- use double slash instead of the dot?