Campus Event Calendar
Event Entry
What and Who
Planar Graphs and Memory Hierarchies - Things We Can('t) Do (Yet?)
Norbert Zeh
Dalhousie Univ. Halifax, Canada
AG1 Mittagsseminar (own work)
AG 1, AG 2, AG 3, AG 4, AG 5
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Wednesday, 10 March 2004
13:30
45 Minutes
46.1 - MPII
024
Saarbrücken
Abstract
This talk gives a survey of algorithmic techniques to solve fundamental
problems on planar graphs I/O-efficiently. The focus is on cache-aware
algorithms that strongly exploit the planarity of the given graphs. In
particular, the talk emphasizes the success of separator-based
approaches, and an I/O-efficient algorithm to compute a separator
decomposition of a planar graph will be discussed. If time permits, a
few problems that arise when trying to make these algorithms
cache-oblivious will be highlighted.
Contact
Ulrich Meyer
--email hidden
passcode not visible
logged in users only
Ulrich Meyer, 03/03/2004 12:27 -- Created document.