]> mj.ucw.cz Git - saga.git/blob - PLAN
More plans.
[saga.git] / PLAN
1 *  Minimum Spanning Trees
2
3   o  The Problem
4   o  Basic properties
5   o  Red/Blue meta-algorithm
6   o  Classical algorithms
7   o  Contractive algorithms
8
9 *  Fine Details of Computation
10
11   o  Models and machines
12   o  Radix-sorting
13   o  Bit tricks
14   o  Q-Heaps
15
16 *  Advanced MST Algorithms
17
18   o  Minor-closed classes
19   o  Fredman-Tarjan algorithm
20   .  MST verification
21   .  Randomized algorithms
22   .  ?? Chazelle ??
23   .  ?? Pettie ??
24
25 *  Ranking combinatorial objects
26
27   o  Ranking and unranking
28   o  Ranking of permutations
29   o  Ranking of k-permutations
30   o  Restricted permutations
31   o  Hatcheck lady and other derangements
32   .  ?? other objects ??
33   .  ?? general perspective ??
34
35 *  Dynamic MST algorithms
36
37   .  (Semi-)dynamic algorithms
38   .  Sleator-Tarjan trees
39   .  ET-trees
40   .  Fully dynamic connectivity
41   .  Semi-dynamic MST
42   .  Fully dynamic MST
43
44 TODO:
45
46 Spanning trees:
47
48 - cite Eisner's tutorial \cite{eisner:tutorial}
49 - \cite{pettie:onlineverify} online lower bound
50 - mention Steiner trees
51 - mention matroids
52 - mention disconnected graphs
53 - Euclidean MST
54 - Some algorithms (most notably Fredman-Tarjan) do not need flattening
55 - reference to mixed Boruvka-Jarnik
56 - use the notation for contraction by a set
57 - practical considerations: katriel:cycle, moret:practice (mention pairing heaps)
58 - parallel algorithms: p243-cole (are there others?)
59
60 Models:
61
62 - bit tricks: reference to HAKMEM
63 - mention in-place radix-sorting?
64 - consequences of Q-Heaps: Thorup's undirected SSSP etc.
65 - add more context from thorup:aczero, also mention FP operations
66 - refs on Cartesian trees
67 - update notation.tex
68
69 Ranking:
70
71 - the general perspective: is it only a technical trick?
72 - ranking of permutations on general sets, relationship with integer sorting
73
74 Notation:
75
76 - \O(...) as a set?
77 - G has to be connected, so m=O(n)
78 - impedance mismatch in terminology: contraction of G along e vs. contraction of e.
79 - use \delta(X) notation
80 - unify use of n(G) vs. n
81 - use calligraphic letters from ams?
82 - change the notation for contractions -- use double slash instead of the dot?