o Fredman-Tarjan algorithm
o MST verification
o Linear-time verification
- . A randomized algorithm
- . ?? Chazelle ??
- . ?? Pettie ??
+ o A randomized algorithm
o Special cases and related problems
-* Ranking combinatorial objects
+* 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
- . ?? other objects ??
- . ?? general perspective ??
-
-* Dynamic MST algorithms
-
- . (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
-- move the remark on disconnected graphs? separate section?
-- 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
-- mention parallel algorithms (see remarks in Karger)
+Applications:
-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
-- expand the section on radix-sorting, mention Buchsbaum
+- degree-restricted cases and arborescences
+- bounded expansion classes?
Ranking:
- 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
+ co je to vlastne za matice co splnuji 4.5.2
- JN: bounded-degree restriction graphs; would it imply general speedup?
-Notation:
+Typography:
-- 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?
-- introduce \widehat\O early
+* formatting of multi-line \algin, \algout
-Varia:
+Global:
-- cite GA booklet
+- each chapter should make clear in which model we work
+- intro: \log is binary