Special cases.

[saga.git] / PLAN

diff --git a/PLAN b/PLAN
index 9e1cb1062ca307ff710d14a369a9cb4e3ae1aab4..40a1092ddea5d97ee7020649d129d1efabff2bd6 100644 (file)
--- a/PLAN
+++ b/PLAN
@@ -10,27 +10,28 @@
 
   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
+  .  ?? Chazelle ??
+  .  ?? Pettie ??
+  o  Special cases and related problems
 
 *  Ranking combinatorial objects
 
-  .  Ranking of permutations: history
-  .  Linear-time algorithm
-  .  k-permutations
-  .  Permutations with no fixed point
+  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
 
@@ -45,33 +46,40 @@ TODO:
 
 Spanning trees:
 
-- 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
+- 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
 
 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
 
 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 vlstne za matice co splnuji 4.5.2
+- JN: bounded-degree restriction graphs; would it imply general speedup?
 
 Notation:
 
-- \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
+- use calligraphic letters from ams?
+- change the notation for contractions -- use double slash instead of the dot?