TODO:
+Preface:
+
+- move TOC to the beginning of the book
+- mention notation
+- cite GA booklet
+
Spanning trees:
- cite Eisner's tutorial \cite{eisner:tutorial}
-- 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
-- use the name "Boruvka step"
+- mention that there are only a few algorithms based on the Red rule
Related:
- practical considerations: katriel:cycle, moret:practice (mention pairing heaps)
- K best trees
- degree-restricted cases and arborescences
- bounded expansion classes?
-- mention matroids
-
-Models:
-
-- add references to the C language
-- PM: unify yardsticks
-- all data structures should mention space complexity
+- finding all MST's
Ranking:
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
Global:
-- Intro: cite GA booklet
- each chapter should make clear in which model we work
- clean up bibliography
+
+Pictures:
+
+- structure of a Q-heap
projects / saga.git / blobdiff