X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=PLAN;h=c8a1a60b3724ecbc71ea1d0a8aafd0536e192d64;hb=c5b57b993ede5af08f88c3dd033021e73ede7e3c;hp=9e1cb1062ca307ff710d14a369a9cb4e3ae1aab4;hpb=be2346beec4fc58ce12daa62022465be3990629d;p=saga.git

diff --git a/PLAN b/PLAN
index 9e1cb10..c8a1a60 100644
--- a/PLAN
+++ b/PLAN
@@ -10,68 +10,63 @@
 
   o  Models and machines
   o  Radix-sorting
-  .  Bit tricks
-  .  Ranking sets
-  .  Bitwise B-trees
-  .  Q-Heaps
+  o  Bit tricks
+  o  Q-Heaps
 
 *  Advanced MST Algorithms
 
   o  Minor-closed classes
   o  Fredman-Tarjan algorithm
-  .  ?? Chazelle ??
-  .  ?? Pettie ??
-  .  MST verification
-  .  Randomized algorithms
+  o  MST verification
+  o  Linear-time verification
+  o  A randomized algorithm
+  o  Special cases and related problems
 
-*  Ranking combinatorial objects
+*  Approaching Optimality
 
-  .  Ranking of permutations: history
-  .  Linear-time algorithm
-  .  k-permutations
-  .  Permutations with no fixed point
-  .  ?? other objects ??
+  o  Soft heaps
+  o  Robust contractions
+  o  Decision trees
+  o  An optimal algorithm
 
 *  Dynamic MST algorithms
 
-  .  (Semi-)dynamic algorithms
-  .  Sleator-Tarjan trees
-  .  ET-trees
-  .  Fully dynamic connectivity
-  .  Semi-dynamic MST
-  .  Fully dynamic MST
+  o  (Semi-)dynamic algorithms
+  o  ET-trees
+  o  Fully dynamic connectivity
+  o  Dynamic MST
+  o  Almost minimum trees
 
-TODO:
+*  Ranking Combinatorial Objects
 
-Spanning trees:
+  o  Ranking and unranking
+  o  Ranking of permutations
+  o  Ranking of k-permutations
+  o  Restricted permutations
+  o  Hatcheck lady and other derangements
 
-- prove the density bound
-- fix proof of the local contraction alg
-- cite Eisner's tutorial \cite{eisner:tutorial}
-- \cite{pettie:onlineverify} online lower bound
-- mention Steiner trees
-- mention matroids
-- sorted weights
-- mention disconnected graphs
-- Euclidean MST
-- Some algorithms (most notably Fredman-Tarjan) do not need flattening
-- reference to mixed Boruvka-Jarnik
+TODO:
 
-Models:
+Applications:
 
-- bit tricks: reference to HAKMEM
-- mention in-place radix-sorting?
+- degree-restricted cases and arborescences
+- bounded expansion classes?
 
 Ranking:
 
 - the general perspective: is it only a technical trick?
-- move description of the ranking set to the chapter on models?
 - 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?
+
+Typography:
+
+* formatting of multi-line \algin, \algout
 
-Notation:
+Global:
 
-- \O(...) as a set?
-- 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
+- each chapter should make clear in which model we work
+- intro: \log is binary