. Randomized algorithms
. ?? Chazelle ??
. ?? Pettie ??
- . Other classes of graphs
+ 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
- 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?)
-- mention 3-regular graphs; bounded expansion?
+- bounded expansion classes?
+- restricted cases and arborescences
Models:
- mention in-place radix-sorting?
- consequences of Q-Heaps: Thorup's undirected SSSP etc.
- add more context from thorup:aczero, also mention FP operations
-- refs on Cartesian trees
-- update notation.tex
Ranking:
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