[Lowerbounds, Upperbounds]

Friday October 27, 2006
Wean 7220, 3:30PM

Buffer Heap: A Cache-Oblivious Priority Queue with Applications to Shortest Path Computations

Vijaya Ramachandran
University of Texas at Austin

We present the Buffer Heap (BH), a cache-oblivious priority queue that supports all traditional priority queue operations as well as the Decrease-Key operation in O((1/B) log n) amortized block transfers (or I/Os) per operation, where B is the (unknown) block size and n is the number of elements on the BH. Using the BH we present shortest path methods based on Dijkstra’s algorithm that are theoretically superior to traditional methods in terms of the number of I/Os performed.

We present experimental results that indicate that BH is faster than other general-purpose priority queues when the number of priority queue operations is reasonably large. We also present experimental results that show that shortest path methods that use BH and its variants are faster on some natural classes of graphs than Dijkstra’s algorithm with traditional general-purpose priority queues.

This is joint work with Rezaul Alam Chowdhury; additionally, Lingling Tong and David Lan Roche contributed to the experimental work.

SPEAKER: Todd Phillips
TIME: Wednesday 12-1pm, October 25, 2006
PLACE: NSH 1507
TITLE: Runtime-Efficient Meshing Algorithms

ABSTRACT:

I will overview the meshing problem in three and higher dimensions, presenting various state of the art algorithmic guarantees on the output. I will present a simple new meshing algorithm, “Sparse Voronoi Refinement” (SVR), that provides near-optimal worst case runtime along with output guarantees. We will explore how packing and structural lemmas lead to a concise, elegant proof of the runtime guarantees. We will discuss more complex extensions of SVR as well as SVR’s implications for future meshing research. This is joint work with Gary Miller and Benoit Hudson.