Bachelor Thesis BCLR-2021-83

BibliographyGüzel, Emre: Verteiltes Subgraph-Counting mit Colorcoding.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Bachelor Thesis No. 83 (2021).
56 pages, german.
Abstract

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.

Full text and
other links
Volltext
Department(s)University of Stuttgart, Institute of Parallel and Distributed Systems, Distributed Systems
Superviser(s)Rothermel, Prof. Kurt; Schramm, Michael
Entry dateApril 27, 2022
   Publ. Department   Publ. Institute   Publ. Computer Science