o ET-trees
o Fully dynamic connectivity
o Dynamic MST
+ o Almost minimum trees
* Ranking Combinatorial Objects
o Ranking of k-permutations
o Restricted permutations
o Hatcheck lady and other derangements
- . ?? other objects ??
- . ?? general perspective ??
TODO:
-Preface:
+Applications:
-- mention notation
-- cite GA booklet
-- mention bugs in Valeria's verification paper
-
-- G has to be connected, so m=O(n)
-
-Spanning trees:
-
-- cite Eisner's tutorial \cite{eisner:tutorial}
-- Some algorithms (most notably Fredman-Tarjan) do not need flattening
-* Lemma: deletion of a non-MST edge does not alter the MST
-
-Related:
-- K best trees
- degree-restricted cases and arborescences
- bounded expansion classes?
-- finding all MST's
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 vlastne za matice co splnuji 4.5.2
- JN: bounded-degree restriction graphs; would it imply general speedup?
-Notation:
-
-- use \delta(X) notation
-- use the notation for contraction by a set
-- unify use of n(G) vs. n
-- introduce \widehat\O early
-
Typography:
-* formatting of multi-line \algin, \algout
-- use calligraphic letters from ams?
-
-Global:
-
-- each chapter should make clear in which model we work
-- clean up bibliography
-
-Pictures:
-
-- structure of a Q-heap
+- formatting of multi-line \algin, \algout