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:
-Spanning trees:
-
-- cite Eisner's tutorial \cite{eisner:tutorial}
-- \cite{pettie:onlineverify} online lower bound
-- move the remark on disconnected graphs? separate section?
-- mention graphs with non-unique weights? also in the separate section?
-- Some algorithms (most notably Fredman-Tarjan) do not need flattening
-- citation of mixed Boruvka-Jarnik
-- use the notation for contraction by a set
-- mention bugs in Valeria's verification paper
-- more references on decision trees
-- rename theorem on Minimality by order
-- introduce Cut rule and Cycle rule earlier
-- Lemma: deletion of a non-MST edge does not alter the MST
-
-Related:
-- practical considerations: katriel:cycle, moret:practice (mention pairing heaps)
-- parallel algorithms: p243-cole (see also remarks in Karger and pettie:minirand), pettie:parallel
-- K best trees
-- random sampling (propp:randommst)
+Applications:
+
- degree-restricted cases and arborescences
- bounded expansion classes?
-- mention matroids
-
-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
-- Tarjan79 is mentioned by Pettie to define Pointer machines
-- add references to the C language
-- PM: unify yardsticks
-- all data structures should mention space complexity
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
+ co je to vlastne 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?
-- introduce \widehat\O early
-- unify { x ; ... }, { x | ...} and { x : ... }
-- capitalize Pointer Machine
-- Ackermann: which of the Tarjan's set union papers should we cite?
-- Ackermann function vs. Ackermann's function
-
-Varia:
+Typography:
-- cite GA booklet
-- minimize the use of Remarks, use \paran instead
- formatting of multi-line \algin, \algout
-- each chapter should make clear in which model we work
projects / saga.git / blobdiff