edoc-Server der Humboldt-Universität zu Berlin

Dissertation

Autor(en): Mariano Zelke
Titel: Algorithms for streaming graphs
Gutachter: Martin Grohe; Stefan Hougardy; Ulrich Meyer
Volltext: pdf (urn:nbn:de:kobv:11-10097652)
Fachgebiet(e): Informatik
Schlagwörter (ger): Datenstrom-Algorithmus, Graph, Minimal Spannender Baum, Matching
Schlagwörter (eng): matching, streaming algorithm, graph, minimum spanning tree
Einrichtung: Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II
Zitationshinweis: Zelke, Mariano: Algorithms for streaming graphs; Dissertation, Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II , publiziert am , urn:nbn:de:kobv:11-10097652
Metadatenexport: Um den gesamten Metadatensatz im Endnote- oder Bibtex-Format zu speichern, klicken Sie bitte auf den entsprechenden Link. Endnote   Bibtex  
print on demand: Wenn Sie auf dieses Icon klicken, können Sie ein Druckexemplar dieser Publikation bestellen.

Abstract (ger):
Für einen Algorithmus zum Lösen eines Graphenproblems wird üblicherweise angenommen, dieser sei mit wahlfreiem Zugriff (random access) auf den Eingabegraphen G ausgestattet, als auch mit einem Arbeitsspeicher, der G vollständig aufzunehmen vermag. Diese Annahmen erweisen sich als fragwürdig, wenn Graphen betrachtet werden, deren Größe jene konventioneller Arbeitsspeicher übersteigt. Solche Graphen können nur auf externen Speichern 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 vorgeschlagen. Dieses Modell beschränkt die Größe des Arbeitsspeichers und verbietet den wahlfreien Zugriff auf den Eingabegraphen G. Im Gegenteil wird angenommen, die Eingabe sei ein Datenstrom bestehend aus Kanten von G 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 Berechnung 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 bekannten Approximationsalgorithmus an. Schließlich zeigen wir, dass sowohl ein minimaler als auch ein maximaler Schnitt in einem Graphen nicht von einem Semi-Streaming Algorithmus berechnet werden kann. Für beide Probleme stellen wir randomisierte Approximationsalgorithmen im Semi-Streaming Modell vor.
Abstract (eng):
An algorithm solving a graph problem is usually expected to have fast random access to the input graph G and a working memory that is able to store G completely. These powerful assumptions are put in question by massive 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 approaching different graph problems. For the problems of testing graph connectivity 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.
Zugriffsstatistik: Die Daten für die Zugriffsstatistik der einzelnen Dokumente wurden aus den durch AWStats aggregierten Webserver-Logs erstellt. Sie beziehen sich auf den monatlichen Zugriff auf den Volltext sowie auf die Startseite. Die Zugriffsstatistik wird nicht standardisiert erfasst und kann maschinelle Zugriffe enthalten.
 
Bei Formatversionen eines Dokuments, die aus mehreren Dateien bestehen (insbesondere HTML), wird jeweils der monatlich höchste Zugriffswert auf eine der Dateien (Kapitel) des Dokuments angezeigt.
 
Um die detaillierten Zugriffszahlen zu sehen, fahren Sie bitte mit dem Mauszeiger über die einzelnen Balken des Diagramms.
Startseite: 4 Zugriffe PDF: 6 Zugriffe Startseite: 3 Zugriffe PDF: 12 Zugriffe Startseite: 8 Zugriffe PDF: 13 Zugriffe Startseite: 4 Zugriffe PDF: 13 Zugriffe Startseite: 3 Zugriffe PDF: 14 Zugriffe PDF: 17 Zugriffe Startseite: 1 Zugriffe PDF: 10 Zugriffe PDF: 21 Zugriffe PDF: 20 Zugriffe Startseite: 1 Zugriffe PDF: 17 Zugriffe Startseite: 3 Zugriffe PDF: 22 Zugriffe Startseite: 2 Zugriffe PDF: 10 Zugriffe PDF: 12 Zugriffe PDF: 19 Zugriffe PDF: 16 Zugriffe PDF: 13 Zugriffe Startseite: 2 Zugriffe PDF: 39 Zugriffe Startseite: 2 Zugriffe PDF: 33 Zugriffe Startseite: 2 Zugriffe PDF: 44 Zugriffe Startseite: 3 Zugriffe PDF: 48 Zugriffe Startseite: 3 Zugriffe PDF: 28 Zugriffe Startseite: 2 Zugriffe PDF: 21 Zugriffe Startseite: 5 Zugriffe PDF: 10 Zugriffe PDF: 22 Zugriffe Startseite: 3 Zugriffe PDF: 22 Zugriffe Startseite: 7 Zugriffe PDF: 29 Zugriffe Startseite: 2 Zugriffe PDF: 21 Zugriffe Startseite: 2 Zugriffe PDF: 15 Zugriffe Startseite: 1 Zugriffe PDF: 37 Zugriffe PDF: 35 Zugriffe Startseite: 2 Zugriffe PDF: 38 Zugriffe PDF: 37 Zugriffe PDF: 53 Zugriffe PDF: 51 Zugriffe Startseite: 3 Zugriffe PDF: 20 Zugriffe PDF: 18 Zugriffe Startseite: 2 Zugriffe PDF: 27 Zugriffe Startseite: 2 Zugriffe PDF: 33 Zugriffe Startseite: 4 Zugriffe PDF: 48 Zugriffe
Jul
11
Aug
11
Sep
11
Oct
11
Nov
11
Dec
11
Feb
12
Apr
12
May
12
Jun
12
Jul
12
Aug
12
Sep
12
Oct
12
Nov
12
Dec
12
Jan
13
Feb
13
Mar
13
Apr
13
May
13
Jun
13
Jul
13
Aug
13
Sep
13
Oct
13
Nov
13
Dec
13
Jan
14
Feb
14
Mar
14
Apr
14
May
14
Jun
14
Jul
14
Aug
14
Sep
14
Oct
14
Nov
14
Monat Jul
11
Aug
11
Sep
11
Oct
11
Nov
11
Dec
11
Feb
12
Apr
12
May
12
Jun
12
Jul
12
Aug
12
Sep
12
Oct
12
Nov
12
Dec
12
Jan
13
Feb
13
Mar
13
Apr
13
May
13
Jun
13
Jul
13
Aug
13
Sep
13
Oct
13
Nov
13
Dec
13
Jan
14
Feb
14
Mar
14
Apr
14
May
14
Jun
14
Jul
14
Aug
14
Sep
14
Oct
14
Nov
14
Startseite 4 3 8 4 3   1     1 3 2         2 2 2 3 3 2 5   3 7 2 2 1   2       3   2 2 4
PDF 6 12 13 13 14 17 10 21 20 17 22 10 12 19 16 13 39 33 44 48 28 21 10 22 22 29 21 15 37 35 38 37 53 51 20 18 27 33 48

Gesamtzahl der Zugriffe seit Jul 2011:

  • Startseite – 76 (1.95 pro Monat)
  • PDF – 964 (24.72 pro Monat)
 
 
Generiert am 18.12.2014, 18:38:18