* Dynamic MST algorithms
- . (Semi-)dynamic algorithms
- . Sleator-Tarjan trees and semi-dynamic MST
- . ET-trees
- . Fully dynamic connectivity
- . Dynamic MST
+ o (Semi-)dynamic algorithms
+ o ET-trees
+ o Fully dynamic connectivity
+ o Dynamic MST
* Ranking Combinatorial Objects
TODO:
+Preface:
+
+- move TOC to the beginning of the book
+- mention notation
+- cite GA booklet
+
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 (see also remarks in Karger and pettie:minirand), pettie:parallel
-- bounded expansion classes?
-- degree-restricted cases and arborescences
-- random sampling (propp:randommst)
- mention bugs in Valeria's verification paper
- more references on decision trees
+- Lemma: deletion of a non-MST edge does not alter the MST
+- mention that there are only a few algorithms based on the Red rule
-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 claimed by Pettie to define Pointer machines
-- add references to the C language
-- PM: unify yardsticks
+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
+- degree-restricted cases and arborescences
+- bounded expansion classes?
+- finding all MST's
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:
+- sort the table
- 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
-- define \alpha(m,n) and use it instead of \alpha(n)
-Varia:
+Typography:
-- cite GA booklet
-- minimize the use of Remarks, use \paran instead
+- 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