Bachelorarbeit BCLR-2021-83

Bibliograph.
Daten
Güzel, Emre: Verteiltes Subgraph-Counting mit Colorcoding.
Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik, Bachelorarbeit Nr. 83 (2021).
56 Seiten, deutsch.
Kurzfassung

Für das Subgraph-Counting-Problem und das Subgraph-Enumeration-Problem sind die Anzahlen und Häufigkeiten der Isomorphismen für bestimmte Subgraphen in größeren Graphen von Interesse. Zur Lösung dieser Probleme gibt es verschiedene Ansätze. Einer dieser Ansätze basiert auf dem Colorcoding [AYZ95] Verfahren von Alon et al. Die beiden Algorithmen PARSE [ZKKM10] und CC [BCK+17] [BCK+18] versuchen diese Probleme mit diesem Ansatz zu lösen. Dabei hat PARSE eine verteilte Version, wohingegen CC lediglich auf einer einzigen Maschine ausführbar ist. Zusätzlich zu diesen beiden Algorithmen wird in dieser Arbeit DistCC, eine verteilte Version CC’s, vorgestellt. DistCC orientiert sich bei der Art und Weise seiner Verteilung am Beispiel von PARSE. Dank der Verteilung sind die Laufzeiten DistCC’s teilweise deutlich kürzer, als die Laufzeiten CC’s. Außerdem wurden neben der natürlichen Sortierung der Graphen auch zwei neue Sortierungen eingeführt, die die Laufzeiten CC’s und somit auch DistCC’s teilweise verbessern.

Volltext und
andere Links
Volltext
Abteilung(en)Universität Stuttgart, Institut für Parallele und Verteilte Systeme, Verteilte Systeme
BetreuerRothermel, Prof. Kurt; Schramm, Michael
Eingabedatum27. April 2022
   Publ. Abteilung   Publ. Institut   Publ. Informatik