MIT Department of Electrical Engineering & Computer Science
An O(log log n) Priority Queue
Mikkel Thorup
University of Copenhagen
Thursday, July 6, 1995
3:45 PM (3:30 refreshments)
Room NE43-518
Theory of Computation Seminar
Abstract
This talk presents a simple RAM priority queue supporting
insert and extract-min operations in worst case time
O(log log n) where n is the current number of keys in the queue.
Priority queues are of direct importance in operating systems, and,
moreover, they are used for greedy algorithms. For example, we now
get an O(n+m log log m) algorithm for the single source shortest path
problem on a graph with n nodes and m edges.
Also, we will discuss some more general theoretical relations between
sorting and priority queues. For example, for any fixed epsilon>0,
these will imply an O(n sqrt{log n}^{1+epsilon}+m) algorithm for
the single source shortest path problem, complementing the above bound.
Host: David Karger
URL of this page:
http://www-eecs.mit.edu/AY95-96/events/1.html
Created: Aug 28, 1995
|
Modified: Jun 25, 1997
This announcement is from the MIT EECS 1995-96 archive.
|
Current events
To MIT EECS home page
|
Your comments
and inquiries are welcome.
