Algorithms for streaming graphs [Elektronische Ressource] / von Mariano Zelke

Algorithms for Streaming GraphsDISSERTATIONzur Erlangung des akademischen Gradesdoctor rerum naturalium(Dr. rer. nat.)im Fach Informatikeingereicht an derMathematisch-Naturwissenschaftlichen Fakultät IIHumboldt-Universität zu BerlinvonHerr Dipl.-Inf. Mariano Zelkegeboren am 12.11.1978 in Lutherstadt WittenbergPräsident der Humboldt-Universität zu Berlin:Prof. Dr. Dr. h.c. Christoph MarkschiesDekan der Mathematisch-Naturwissenschaftlichen Fakultät II:Prof. Dr. Wolfgang CoyGutachter:1. Prof. Dr. Martin Grohe2. Prof. Dr. Stefan Hougardy3. Prof. Dr. Ulrich Meyereingereicht am: 13.11.2008Tag der mündlichen Prüfung: 18.02.2009AbstractAn algorithm solving a graph problem is usually expected to have fast ran-dom access to the input graph G and a working memory that is able tostoreG completely. These powerful assumptions are put in question by mas-sive graphs that exceed common working memories and that can only bestored on disks or even tapes. Here, random access is very time-consuming.To tackle massive graphs stored on external memories, Muthukrishnanproposed the semi-streaming model in 2003. It permits a working memoryof restricted size and forbids random access to the input graph. In contrast,the input is assumed to be a stream of edges in arbitrary order.In this thesis we develop algorithms in the semi-streaming model ap-proaching different graph problems.