Campus Event Calendar
Event Entry
What and Who
Heuristics for Average Diameter Approximation with External Memory Algorithms
Irina Brudaru
IMPRS
Masterseminar/Talk
AG 1, AG 2, AG 3, AG 4, AG 5, SWS, RG1, RG2
Public Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Tuesday, 23 October 2007
13:00
30 Minutes
E1 4
024
Saarbrücken
Abstract
Many large scale applications need data sets too large to fit completely inside a computer's internal memory. Thus the input/output (I/O) communication between the fast internal memory and the slow external memory (disks) can create a performance bottleneck. That is where the I/O operation efficient algorithms solve such problems that involve large data structures.
Given that there are already different methods proposed for solving the breadth first search (BFS) problem on very large graphs, for example Munagala-Ranade and Mehlhorn-Meyer randomized BFS, this thesis proposes to expand the work done in this direction and experiment with a distinct approach. In this thesis we propose different randomized heuristics for approximating the average diameter of various large graph classes, using external memory algorithms.
Contact
IMPRS
9325225
--email hidden
passcode not visible
logged in users only
Andrea Primm, 09/18/2007 11:00
Andrea Primm, 09/18/2007 11:00 -- Created document.
Andrea Primm, 09/18/2007 11:00 -- Created document.