Event Entry
What and Who
Single Source Shortest Path in Random Graphs - Algorithms for PRAM, BSP and External Memory
Date, Time and Location
Abstract
on a large class of random input graphs with non-negative edge
weights. Based on two observations concerning the possibility of
multi-deletes from the priority queue in Dijkstra's algorithm and
concerning expansion in random graphs we derive novel algorithms
for the PRAM, BSP and external memory model.
In particular we give the first O( n log n + m ) work(-optimal)
CRCW PRAM algorithm with sublinear running time T for a large
class of sparse random graphs with edges costs uniformly
distributed in [0,1]: it achieves T=O( sqrt(m) log^2 n ) with
high probability, where n,m are the number of nodes respectively
the number of edges in the graph.
Using similar ideas gives rise to a BSP algorithm which
performs on p processors O( sqrt(m) log p ) supersteps.
Each superstep involves routing an h-relation where h is
bounded by O( sqrt(m)/p + log^2 n ) with high probability.
In the external memory model we present an algorithm that uses
O( n/D + m/(DB) log_{S/B} m/B ) I/O with high probability.
Here S denotes the size of available internal memory, B is the
size of block transfer and D is the number of independent parallel
disks; D is constrained to be O( min{ S/B , n/(sqrt(m) log n) } ).
Contact