]> mj.ucw.cz Git - saga.git/blob - PLAN
Minor improvements.
[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 Preface:
52
53 - move TOC to the beginning of the book
54 - mention notation
55 - cite GA booklet
56
57 Spanning trees:
58
59 - cite Eisner's tutorial \cite{eisner:tutorial}
60 - Some algorithms (most notably Fredman-Tarjan) do not need flattening
61 - use the notation for contraction by a set
62 - mention bugs in Valeria's verification paper
63 - more references on decision trees
64 - Lemma: deletion of a non-MST edge does not alter the MST
65 - mention that there are only a few algorithms based on the Red rule
66
67 Related:
68 - practical considerations: katriel:cycle, moret:practice (mention pairing heaps)
69 - parallel algorithms: p243-cole (see also remarks in Karger and pettie:minirand), pettie:parallel
70 - K best trees
71 - degree-restricted cases and arborescences
72 - bounded expansion classes?
73 - finding all MST's
74
75 Ranking:
76
77 - the general perspective: is it only a technical trick?
78 - ranking of permutations on general sets, relationship with integer sorting
79 - JN: explain approx scheme
80 - JN: 4.5.1:  neslo by preci isolovat nejaky vlstnosti restriction matrices
81   tak aby byl speedup? Staci napr predpokladat 4.5.2 (jako to postulovat)
82   co je to vlastne za matice co splnuji 4.5.2
83 - JN: bounded-degree restriction graphs; would it imply general speedup?
84
85 Notation:
86
87 - sort the table
88 - G has to be connected, so m=O(n)
89 - impedance mismatch in terminology: contraction of G along e vs. contraction of e.
90 - use \delta(X) notation
91 - unify use of n(G) vs. n
92 - change the notation for contractions -- use double slash instead of the dot?
93 - introduce \widehat\O early
94
95 Typography:
96
97 - formatting of multi-line \algin, \algout
98 - use calligraphic letters from ams?
99
100 Global:
101
102 - each chapter should make clear in which model we work
103 - clean up bibliography
104
105 Pictures:
106
107 - structure of a Q-heap