]> mj.ucw.cz Git - saga.git/blob - PLAN
Corrections to the intro to dynamic algorithms.
[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   o  Soft heaps
28   o  Robust contractions
29   o  Decision trees
30   o  An optimal algorithm
31
32 *  Dynamic MST algorithms
33
34   o  (Semi-)dynamic algorithms
35   o  ET-trees
36   o  Fully dynamic connectivity
37   o  Dynamic MST
38
39 *  Ranking Combinatorial Objects
40
41   o  Ranking and unranking
42   o  Ranking of permutations
43   o  Ranking of k-permutations
44   o  Restricted permutations
45   o  Hatcheck lady and other derangements
46   .  ?? other objects ??
47   .  ?? general perspective ??
48
49 TODO:
50
51 Spanning trees:
52
53 - cite Eisner's tutorial \cite{eisner:tutorial}
54 - \cite{pettie:onlineverify} online lower bound
55 - move the remark on disconnected graphs? separate section?
56 - mention graphs with non-unique weights? also in the separate section?
57 - Some algorithms (most notably Fredman-Tarjan) do not need flattening
58 - citation of mixed Boruvka-Jarnik
59 - use the notation for contraction by a set
60 - mention bugs in Valeria's verification paper
61 - more references on decision trees
62 - rename theorem on Minimality by order
63 - introduce Cut rule and Cycle rule earlier
64 - Lemma: deletion of a non-MST edge does not alter the MST
65
66 Related:
67 - practical considerations: katriel:cycle, moret:practice (mention pairing heaps)
68 - parallel algorithms: p243-cole (see also remarks in Karger and pettie:minirand), pettie:parallel
69 - K best trees
70 - random sampling (propp:randommst)
71 - degree-restricted cases and arborescences
72 - bounded expansion classes?
73 - mention matroids
74
75 Models:
76
77 - bit tricks: reference to HAKMEM
78 - mention in-place radix-sorting?
79 - consequences of Q-Heaps: Thorup's undirected SSSP etc.
80 - add more context from thorup:aczero, also mention FP operations
81 - Tarjan79 is mentioned by Pettie to define Pointer machines
82 - add references to the C language
83 - PM: unify yardsticks
84 - all data structures should mention space complexity
85
86 Dynamic:
87
88 - What is the origin of the semidynamic MSF?
89 - lower bounds
90
91 Ranking:
92
93 - the general perspective: is it only a technical trick?
94 - ranking of permutations on general sets, relationship with integer sorting
95 - JN: explain approx scheme
96 - JN: 4.5.1:  neslo by preci isolovat nejaky vlstnosti restriction matrices
97   tak aby byl speedup? Staci napr predpokladat 4.5.2 (jako to postulovat)
98   co je to vlstne za matice co splnuji 4.5.2
99 - JN: bounded-degree restriction graphs; would it imply general speedup?
100
101 Notation:
102
103 - G has to be connected, so m=O(n)
104 - impedance mismatch in terminology: contraction of G along e vs. contraction of e.
105 - use \delta(X) notation
106 - unify use of n(G) vs. n
107 - use calligraphic letters from ams?
108 - change the notation for contractions -- use double slash instead of the dot?
109 - introduce \widehat\O early
110 - unify { x ; ... }, { x | ...} and { x : ... }
111 - capitalize Pointer Machine
112 - Ackermann: which of the Tarjan's set union papers should we cite?
113 - Ackermann function vs. Ackermann's function
114
115 Varia:
116
117 - cite GA booklet
118 - minimize the use of Remarks, use \paran instead