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

-

English
93 pages
Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

Description

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.

Sujets

Informations

Publié par
Publié le 01 janvier 2009
Nombre de lectures 32
Langue English
Signaler un problème
Algorithms
for
Streaming
DISSERTATION
Graphs
zur Erlangung des akademischen Grades doctor rerum naturalium (Dr. rer. nat.) im Fach Informatik
eingereicht an der Mathematisch-NaturwissenschaftlichenFakultätII Humboldt-Universität zu Berlin
von Herr Dipl.-Inf. Mariano Zelke geboren am 12.11.1978 in Lutherstadt Wittenberg
Präsident der Humboldt-Universität zu Berlin: Prof. Dr. Dr. h.c. Christoph Markschies Dekan der Mathematisch-Naturwissenschaftlichen Fakultät II: Prof. Dr. Wolfgang Coy Gutachter:
1. Prof. Dr. Martin Grohe 2. Prof. Dr. Stefan Hougardy 3. Prof. Dr. Ulrich Meyer
eingereicht am: Tag der mündlichen Prüfung:
13.11.2008 18.02.2009
Abstract
An algorithm solving a graph problem is usually expected to have fast ran-dom access to the input graphGand a working memory that is able to storeG powerful assumptions are put in question by mas-completely. These sive graphs that exceed common working memories and that can only be stored on disks or even tapes. Here, random access is very time-consuming. To tackle massive graphs stored on external memories, Muthukrishnan proposed the semi-streaming model in 2003. It permits a working memory of 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. For the problems of testing graph con-nectivity and bipartiteness and for the computation of a minimum spanning tree, we show how to obtain running times that are asymptotically optimal. For the problem of finding a maximum weighted matching, which is known to be intractable in the semi-streaming model, we present the best known approximation algorithm. Finally, we show the minimum and the maximum cut problem in a graph both to be intractable in the semi-streaming model and give semi-streaming algorithms that approximate respective solutions in a randomized fashion.
Keywords: streaming algorithm, graph, minimum spanning tree, matching
Zusammenfassung
Für einen Algorithmus zum Lösen eines Graphenproblems wird üblicherwei-se angenommen, dieser sei mit wahlfreiem Zugriff (random access) auf den EingabegraphenGausgestattet, als auch mit einem Arbeitsspeicher, derG vollständig aufzunehmen vermag. Diese Annahmen erweisen sich als frag-würdig, wenn Graphen betrachtet werden, deren Gröe jene konventioneller Arbeitsspeicher übersteigt. Solche Graphen können nur auf externen Spei-chern wie Festplatten oder Magnetbändern vorrätig gehalten werden, auf denen wahlfreier Zugriff sehr zeitaufwändig ist. Um riesige Graphen zu bearbeiten, die auf externen Speichern liegen, hat Muthukrishnan 2003 das Modell eines Semi-Streaming Algorithmus vorge-schlagen. Dieses Modell beschränkt die Gröe des Arbeitsspeichers und ver-bietet den wahlfreien Zugriff auf den EingabegraphenG. Im Gegenteil wird angenommen, die Eingabe sei ein Datenstrom bestehend aus Kanten vonG in beliebiger Reihenfolge. In der vorliegenden Dissertation entwickeln wir Algorithmen im Semi-Streaming Modell für verschiedene Graphenprobleme. Für das Testen des Zusammenhangs und der Bipartität eines Graphen, als auch für die Berech-nung eines minimal spannenden Baumes stellen wir Algorithmen vor, die asymptotisch optimale Laufzeiten erreichen. Es ist bekannt, dass kein Semi-Streaming Algorithmus existieren kann, der ein grötes gewichtetes Matching in einem Graphen findet. Für dieses Problem geben wir den besten bekann-ten Approximationsalgorithmus an. Schlielich zeigen wir, dass sowohl ein minimaler als auch ein maximaler Schnitt in einem Graphen nicht von ei-nem Semi-Streaming Algorithmus berechnet werden kann. Für beide Proble-me stellen wir randomisierte Approximationsalgorithmen im Semi-Streaming Modell vor.
Schlagwörter: Datenstrom-Algorithmus, Graph, Minimal Spannender Baum, Matching
to my wife
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
13
9
.
13
5
1
.
.
.
.
.
.
4.2.3
.
.
.
.
.
.
.
.
.
.
.
.
4.2.2
18
k .-Vertex Connectivity
.
.
.
.
.
.
.
.
.
.
.
.
Bipartition . . . . . . . .
4.2.1
.
.
.
.
.
.
.
.
Connected Components
.
.
.
.
.
.
.
.
.
.
.
4.1
Optimal Per-Edge
. . . . . . . . .
Introduction . .
.
.
Processing Times
17
.
.
.
.
. . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
22
.
.
.
.
.
4.2.5
20
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Minimum Spanning Forest
20
4.2.4
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
18
k-Edge Connectivity . .
.
.
.
.
Closure . . .
. . .
15
4.3
.
.
.
.
.
.
.
.
.
Certificates and Buffered Edges
4.2
.
.
.
.
.
.
Introduction . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
5.1
.
.
.
.
.
.
.
.
The Algorithm . . .
.
.
.
.
Weighted Matching
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
5.2
.
.
.
.
.
.
.
Approximation Ratio
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
5.3
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
30
6
.
.
25
25
26
45
.
.
Closure
5.4
2
Introduction
3
Related Work
2.1
Discussion on
1
The Semi-Streaming Model
Processing
Time
the
Per-Edge
.
.
.
.
5
4
Contents