University of Konstanz
Graduiertenkolleg / PhD Program
Computer and Information Science

Colloquium of the Department and the PhD Program

title

Algorithm Engineering Methoden für Graphpartitionierung und kürzeste Wege

speaker

Prof. Dr. Dorothea Wagner, University Karlsruhe
Karlsruhe, Germany

date & place

Wednesday, 12.07.2006, 16:15 h
Room C252

abstract

Already more than twenty years ago, the first electronic timetable information systems for European railways or local traffic were established in Europe. Since then, the size of the data contained in such systems as well as the number of queries to be processed have increased dramatically. Nowadays timetable information is concerned with a query-intensive scenario where a central server is directly accessible to any customer either through terminals in train stations or through a web interface, and has to answer a potentially infinite number of queries. Considering the algorithmic core problem of such a system, the main goal is to reduce the average response time for a query by reducing the search space for the shortest-paths computation.

In this talk, we present techniques to reduce the search space for shortest-path computations. More precisely, we examine how precomputed information can be used to speedup Dijkstra's algorithm. Two kinds of speedup techniques are discussed, approaches using node- or edge-labels and hierarchical methods.

The second part of the talk is concerned with graph decomposition, a central aspect of hierarchical speedup techniques as well as divide-and-conquer algorithms in general. We present an experimental study of decomposition techniques based on node selection. Moreover, we give a systematic evaluation of the classical planar separator approach.