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

diff --git a/PLAN b/PLAN
index 05c1bc1..900e7bd 100644
--- a/PLAN
+++ b/PLAN
@@ -19,54 +19,38 @@
   o  Fredman-Tarjan algorithm
   o  MST verification
   o  Linear-time verification
-  .  A randomized algorithm
-  .  ?? Chazelle ??
-  .  ?? Pettie ??
+  o  A randomized algorithm
   o  Special cases and related problems
 
-*  Ranking combinatorial objects
+*  Approaching Optimality
+
+  o  Soft heaps
+  o  Robust contractions
+  o  Decision trees
+  o  An optimal algorithm
+
+*  Dynamic MST algorithms
+
+  o  (Semi-)dynamic algorithms
+  o  ET-trees
+  o  Fully dynamic connectivity
+  o  Dynamic MST
+  o  Almost minimum trees
+
+*  Ranking Combinatorial Objects
 
   o  Ranking and unranking
   o  Ranking of permutations
   o  Ranking of k-permutations
   o  Restricted permutations
   o  Hatcheck lady and other derangements
-  .  ?? other objects ??
-  .  ?? general perspective ??
-
-*  Dynamic MST algorithms
-
-  .  (Semi-)dynamic algorithms
-  .  Sleator-Tarjan trees
-  .  ET-trees
-  .  Fully dynamic connectivity
-  .  Semi-dynamic MST
-  .  Fully dynamic MST
 
 TODO:
 
-Spanning trees:
-
-- cite Eisner's tutorial \cite{eisner:tutorial}
-- \cite{pettie:onlineverify} online lower bound
-- mention matroids
-- mention disconnected graphs
-- 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 (are there others?)
-- bounded expansion classes?
-- restricted cases and arborescences
-- mention randomized algorithms (see remarks in Karger)
+Applications:
 
-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
-- expand the section on radix-sorting, mention Buchsbaum
+- degree-restricted cases and arborescences
+- bounded expansion classes?
 
 Ranking:
 
@@ -75,19 +59,15 @@ 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:
+Typography:
 
-- 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
+* formatting of multi-line \algin, \algout
 
-Varia:
+Global:
 
-- cite GA booklet
+- each chapter should make clear in which model we work
+- clean up bibliography
+- intro: \log is binary