Approaching Optimality. Very slowly.

[saga.git] / PLAN

diff --git a/PLAN b/PLAN
index 42c81f27f432a951e15c53ac125b84b1dcf27c8d..0df70906201150d0ce249524ae314ad5a852777d 100644 (file)
--- a/PLAN
+++ b/PLAN
@@ -20,11 +20,16 @@
   o  MST verification
   o  Linear-time verification
   o  A randomized algorithm
-  .  ?? Chazelle ??
-  .  ?? Pettie ??
   o  Special cases and related problems
 
-*  Ranking combinatorial objects
+*  Approaching Optimality
+
+  .  Soft heaps
+  .  Robust contractions
+  .  An optimal algorithm
+  .  Decision trees
+
+*  Ranking Combinatorial Objects
 
   o  Ranking and unranking
   o  Ranking of permutations
@@ -57,8 +62,9 @@ Spanning trees:
 - practical considerations: katriel:cycle, moret:practice (mention pairing heaps)
 - parallel algorithms: p243-cole (see also remarks in Karger and pettie:minirand), pettie:parallel
 - bounded expansion classes?
-- restricted cases and arborescences
+- degree-restricted cases and arborescences
 - Pettie's paper on random bits (pettie:minirand)
+- random sampling (propp:randommst)
 
 Models:
 
@@ -67,6 +73,7 @@ Models:
 - 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
+- move Q-Heaps to the chapter on the MST's?
 
 Ranking: