a. Monge heap operations: Revealing columns and hiding rows
b. Range minimum queries
c. Monge heap implementation
d. High-level overview of FR-Dijkstra
e. Monge structure of nice r-divisions
f. FR-Dijkstra data structures; Monge heaps, piece heaps and the global heap
g. FR-Dijkstra algorithm and analysis
(Ran out of time for O(n log log n)-time minimum cuts; see lecture notes.)
…Read more
Less…