Special cases.

[saga.git] / PLAN

diff --git a/PLAN b/PLAN
index 8ea33fa441ec4aeb4e1489b3a810f100ebc1f1b8..40a1092ddea5d97ee7020649d129d1efabff2bd6 100644 (file)
--- a/PLAN
+++ b/PLAN
@@ -21,6 +21,7 @@
   .  Randomized algorithms
   .  ?? Chazelle ??
   .  ?? Pettie ??
+  o  Special cases and related problems
 
 *  Ranking combinatorial objects
 
@@ -47,15 +48,15 @@ Spanning trees:
 
 - cite Eisner's tutorial \cite{eisner:tutorial}
 - \cite{pettie:onlineverify} online lower bound
-- mention Steiner trees
 - mention matroids
 - 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:
 
@@ -63,17 +64,19 @@ Models:
 - mention in-place radix-sorting?
 - consequences of Q-Heaps: Thorup's undirected SSSP etc.
 - add more context from thorup:aczero, also mention FP operations
-- refs on Cartesian trees
-- update notation.tex
 
 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 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