X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=PLAN;h=900e7bd72a4bafd6b3414297ceb6c5e70feb6b0c;hb=6659c33a805c0e22c969a45480c068d5d7ddf471;hp=643251f35ec4d5cce9216acf832daf3be71d4550;hpb=6f68c3cceeba460fe5bb689bbdecfe111b992db0;p=saga.git

diff --git a/PLAN b/PLAN
index 643251f..900e7bd 100644
--- a/PLAN
+++ b/PLAN
@@ -35,6 +35,7 @@
   o  ET-trees
   o  Fully dynamic connectivity
   o  Dynamic MST
+  o  Almost minimum trees
 
 *  Ranking Combinatorial Objects
 
@@ -43,34 +44,13 @@
   o  Ranking of k-permutations
   o  Restricted permutations
   o  Hatcheck lady and other derangements
-  .  ?? other objects ??
-  .  ?? general perspective ??
 
 TODO:
 
-Preface:
+Applications:
 
-- move TOC to the beginning of the book
-- mention notation
-- cite GA booklet
-
-Spanning trees:
-
-- cite Eisner's tutorial \cite{eisner:tutorial}
-- Some algorithms (most notably Fredman-Tarjan) do not need flattening
-- use the notation for contraction by a set
-- 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
-
-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:
 
@@ -82,22 +62,12 @@ Ranking:
   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
-- change the notation for contractions -- use double slash instead of the dot?
-- introduce \widehat\O early
-
 Typography:
 
-- formatting of multi-line \algin, \algout
-- use calligraphic letters from ams?
+* formatting of multi-line \algin, \algout
 
 Global:
 
 - each chapter should make clear in which model we work
 - clean up bibliography
+- intro: \log is binary