Not logged in.

Quick Search - Contribution

Contribution Details

Type Master's Thesis
Scope Discipline-based scholarship
Title Different Approaches to Supporting Connectivity Queries on Undirected Fully-Dynamic Graphs
Organization Unit
Authors
  • Alexander Schindler
Supervisors
  • Sven Helmer
  • Qing Chen
Institution University of Zurich
Faculty Faculty of Business, Economics and Informatics
Date 2021
Abstract Text Connectivity queries are among the basic queries on a graph, but there is no trivial way to implement them for fully-dynamic graphs. In the last decades this has been a popular problem in theoretical computer science: a number of data structures have been proposed, but many of them have not been implemented and tested. In this paper three different approaches are explained and discussed: a brute-force approach, an algorithm based on directed rooted trees (IDRFA), and a simpler version of an algorithm that Wulff-Nilsen suggested. For each algorithm we present an implementation and show the algorithm’s performance. The experiments reveal that the the performance depends a lot on the graph’s structure and the application’s actual needs in terms of which operations happen at which frequency.
Zusammenfassung Abfragen, ob zwei Knoten verbunden sind, gehören zu den grundlegenden Abfragen auf einem Graphen, aber es gibt keine triviale Art, diese zu implementieren für dynamische Graphen. In den letzten Jahrzehnten war dies immer wieder ein populäres Problem der theoretischen Informatik: eine grosse Anzahl Datenstrukturen sind vorgeschlagen worden, aber viele von ihnen sind nicht implementiert und getestet worden. In dieser Arbeit werden drei verschiedene Ansätze erklärt und diskutiert: ein Brute-Force-Ansatz, ein Algorithmus, der sich auf gerichtete, gewurzelte Bäume (Out-Trees) stützt (IDRFA), und eine vereinfachte Version eines von Wulff-NIlsen vorgeschlagenen Algorithmus. Für jeden Algorithmus präsentieren wir eine Implementierung und zeigen dann anhand von Experimenten die Performance auf. Die Experimente zeigen, dass die Performance stark von der Struktur des Graphen abhängt wie auch von den tatsächlichen Bedürfnissen der Anwendung, was die Häufigkeit der verschiedenen Operationen und Abfragen angeht.
PDF File Download
Export BibTeX