o Models and machines
o Radix-sorting
o Bit tricks
- . Ranking sets
- . Bitwise B-trees
- . Q-Heaps
+ o Q-Heaps
* Advanced MST Algorithms
o Minor-closed classes
o Fredman-Tarjan algorithm
- . ?? Chazelle ??
- . ?? Pettie ??
. MST verification
. Randomized algorithms
+ . ?? Chazelle ??
+ . ?? Pettie ??
+ o Special cases and related problems
* Ranking combinatorial objects
- cite Eisner's tutorial \cite{eisner:tutorial}
- \cite{pettie:onlineverify} online lower bound
-- mention Steiner trees
- mention matroids
-- sorted weights
- 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:
- bit tricks: reference to HAKMEM
- mention in-place radix-sorting?
+- consequences of Q-Heaps: Thorup's undirected SSSP etc.
+- add more context from thorup:aczero, also mention FP operations
Ranking:
- the general perspective: is it only a technical trick?
- ranking of permutations on general sets, relationship with integer sorting
-- mention approximation of permanent
-- use \pi[x...y]
+- 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
projects / saga.git / blobdiff