Minor improvements.

[saga.git] / PLAN

diff --git a/PLAN b/PLAN
index 6ef6e4f25a067a897c02638feeb69a9522a42478..41930d069e731a846e0d6faa45c951c313c4d0e4 100644 (file)
--- a/PLAN
+++ b/PLAN
@@ -1,36 +1,107 @@
-*  Minimum spanning trees
+*  Minimum Spanning Trees
 
+  o  The Problem
   o  Basic properties
   o  Red/Blue meta-algorithm
   o  Classical algorithms
-  o  Fredman-Tarjan algorithm
-  o  ?? Chazelle ??
-  o  ?? Pettie ??
-  o  Minor-closed classes
-  o  MST verification
-  o  Randomized algorithms
+  o  Contractive algorithms
 
-*  Integer data structures
+*  Fine Details of Computation
 
-  o  Models of computation
+  o  Models and machines
+  o  Radix-sorting
   o  Bit tricks
-  o  Ranking sets
-  o  Bitwise B-trees
   o  Q-Heaps
 
-*  Ranking combinatorial objects
+*  Advanced MST Algorithms
+
+  o  Minor-closed classes
+  o  Fredman-Tarjan algorithm
+  o  MST verification
+  o  Linear-time verification
+  o  A randomized algorithm
+  o  Special cases and related problems
 
-  o  Ranking of permutations: history
-  o  Linear-time algorithm
-  o  k-permutations
-  o  Permutations with no fixed point
-  o  ?? other objects ??
+*  Approaching Optimality
+
+  o  Soft heaps
+  o  Robust contractions
+  o  Decision trees
+  o  An optimal algorithm
 
 *  Dynamic MST algorithms
 
   o  (Semi-)dynamic algorithms
-  o  Sleator-Tarjan trees
   o  ET-trees
   o  Fully dynamic connectivity
-  o  Semi-dynamic MST
-  o  Fully dynamic MST
+  o  Dynamic MST
+
+*  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 ??
+
+TODO:
+
+Preface:
+
+- 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:
+
+- 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:
+
+- 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?
+
+Global:
+
+- each chapter should make clear in which model we work
+- clean up bibliography
+
+Pictures:
+
+- structure of a Q-heap