]> mj.ucw.cz Git - saga.git/blob - PLAN
Approaching Optimality. Very slowly.
[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   o  MST verification
21   o  Linear-time verification
22   o  A randomized algorithm
23   o  Special cases and related problems
24
25 *  Approaching Optimality
26
27   .  Soft heaps
28   .  Robust contractions
29   .  An optimal algorithm
30   .  Decision trees
31
32 *  Ranking Combinatorial Objects
33
34   o  Ranking and unranking
35   o  Ranking of permutations
36   o  Ranking of k-permutations
37   o  Restricted permutations
38   o  Hatcheck lady and other derangements
39   .  ?? other objects ??
40   .  ?? general perspective ??
41
42 *  Dynamic MST algorithms
43
44   .  (Semi-)dynamic algorithms
45   .  Sleator-Tarjan trees
46   .  ET-trees
47   .  Fully dynamic connectivity
48   .  Semi-dynamic MST
49   .  Fully dynamic MST
50
51 TODO:
52
53 Spanning trees:
54
55 - cite Eisner's tutorial \cite{eisner:tutorial}
56 - \cite{pettie:onlineverify} online lower bound
57 - mention matroids
58 - move the remark on disconnected graphs? separate section?
59 - Some algorithms (most notably Fredman-Tarjan) do not need flattening
60 - reference to mixed Boruvka-Jarnik
61 - use the notation for contraction by a set
62 - practical considerations: katriel:cycle, moret:practice (mention pairing heaps)
63 - parallel algorithms: p243-cole (see also remarks in Karger and pettie:minirand), pettie:parallel
64 - bounded expansion classes?
65 - degree-restricted cases and arborescences
66 - Pettie's paper on random bits (pettie:minirand)
67 - random sampling (propp:randommst)
68
69 Models:
70
71 - bit tricks: reference to HAKMEM
72 - mention in-place radix-sorting?
73 - consequences of Q-Heaps: Thorup's undirected SSSP etc.
74 - add more context from thorup:aczero, also mention FP operations
75 - expand the section on radix-sorting, mention Buchsbaum
76 - move Q-Heaps to the chapter on the MST's?
77
78 Ranking:
79
80 - the general perspective: is it only a technical trick?
81 - ranking of permutations on general sets, relationship with integer sorting
82 - JN: explain approx scheme
83 - JN: 4.5.1:  neslo by preci isolovat nejaky vlstnosti restriction matrices
84   tak aby byl speedup? Staci napr predpokladat 4.5.2 (jako to postulovat)
85   co je to vlstne za matice co splnuji 4.5.2
86 - JN: bounded-degree restriction graphs; would it imply general speedup?
87
88 Notation:
89
90 - G has to be connected, so m=O(n)
91 - impedance mismatch in terminology: contraction of G along e vs. contraction of e.
92 - use \delta(X) notation
93 - unify use of n(G) vs. n
94 - use calligraphic letters from ams?
95 - change the notation for contractions -- use double slash instead of the dot?
96 - introduce \widehat\O early
97
98 Varia:
99
100 - cite GA booklet