ICS Theory Group

ICS 269, Winter 2004: Theory Seminar


12 Mar 2004:
Meldable RAM priority queues and minimum spanning trees
Jeremy Yu Meng

The authors describe two general techniques for transforming non-meldable priority queues into meldable ones. Using the resultant priority queues of the first type, they obtain improved algorithms for finding minimum directed spanning trees in graphs with integer weights.

From Meldable RAM priority queues and minimum spanning trees, from SODA '04, by Ran Mendelson, Mikkel Thorup, and Uri Zwick (pages 40--48 in the proceedings).