All Pairs Shortest Path Problem -- Crossroads in Computer Science

Professor Tadao Takaoka

Dept. of CSSE, University of Canterbury

Fri Aug 25 15:10:00 NZST 2006 in Room 031, MSCS

Abstract

The all pairs shortest path problem (APSP) is a crossroads in computer science, where various concepts meet and are tested. I discuss recent developments in algorithms for the APSP from the following perspectives, and introduce some open problems for possible post-graduate projects.

Algebraic structures for APSP: semi-ring, ring, field, Boolean algebra Data structures for APSP: binary heaps, Fibonacci heaps, 2-3 heaps Algorithm analysis paradigms: amortised analysis, probabilistic analysis Algorithm design paradigms: divide and concur, dynamic programming, preprocessing Parallel algorithms for APSP: RAM model, mesh algorithms Applications of APSP: facility location, maximum subarray, car navigation