o MST verification
o Linear-time verification
o A randomized algorithm
- . ?? Chazelle ??
- . ?? Pettie ??
o Special cases and related problems
-* Ranking combinatorial objects
+* Approaching Optimality
+
+ . Soft heaps
+ . Robust contractions
+ . An optimal algorithm
+ . Decision trees
+
+* Ranking Combinatorial Objects
o Ranking and unranking
o Ranking of permutations
- practical considerations: katriel:cycle, moret:practice (mention pairing heaps)
- parallel algorithms: p243-cole (see also remarks in Karger and pettie:minirand), pettie:parallel
- bounded expansion classes?
-- restricted cases and arborescences
+- degree-restricted cases and arborescences
- Pettie's paper on random bits (pettie:minirand)
+- random sampling (propp:randommst)
Models:
- consequences of Q-Heaps: Thorup's undirected SSSP etc.
- add more context from thorup:aczero, also mention FP operations
- expand the section on radix-sorting, mention Buchsbaum
+- move Q-Heaps to the chapter on the MST's?
Ranking: