X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=PLAN;h=51732fb331fc7803759ef613346fbaae697aedb1;hb=ffb37804836177acfd7636b71724fd2fe732a295;hp=6ee8b132f5d734f243ceafbecd12d8ffd3f88207;hpb=88938d05d7e5c24c276fbdb7ca584e4fa7c98d96;p=saga.git

diff --git a/PLAN b/PLAN
index 6ee8b13..51732fb 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,58 +44,22 @@
   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