Campus Event Calendar
Event Entry
What and Who
among other things: External Memory BFS on Undirected Graphs with Bounded Degree
mainly Ulrich Meyer
Max-Planck-Institut für Informatik - AG 1
SIG Meeting
AG 1
AG Audience
-- Not specified --
Note: We use this to send email in the morning.
Date, Time and Location
Friday, 19 May 2000
13:30
-- Not specified --
46
007
Saarbrücken
Abstract
We give the first external memory algorithm for breadth-first
search (BFS) which breaks the Omega(n) I/O bound on arbitrary
undirected graphs with n nodes and constant maximum node degree d.
Our algorithm needs O( n * (1+a) / (b * log_d B) ) I/Os
for main memory size M, n <= M^{1+a}, block size B <= M^{1-b}
and arbitrary constants a,b > 0. The result carries over to
single source shortest paths (SSSP) on undirected planar
graphs with bounded degree.
Contact
Jop F. Sibeyn
--email hidden
passcode not visible
logged in users only
Tags, Category, Keywords and additional notes