Implementing Fast Flows via MAOs

Supervisor: Jens M. Schmidt

Flows are everywhere - when calculating the amount of fluids that pass through pipelines, rounding demographic statistics or trying to find the next pit to remove in open pit mining - most of what matters for these problems can be modeled by computing a maximum flow in a graph.

In this master thesis, we aim at implementing maximum flow algorithms that allow for large-scale computation and that are competitive in speed to the state of the art implementations that are available today. As a novel approach, we try to use structural insights of maximal adjacency orderings to outperform standard implementations. This thesis therefore needs you to have

  • a profound knowledge of C++,
  • skill in writing efficient C++ code for algorithms and the underlying graph data structure,
  • familiarity with graphs, and interest in graph theory and algorithms.

The resulting implementation of this thesis shall be made available open-source and platform-independent. If you are interested in this thesis, please contact me by email.

 


 

Betreuer: Jens M. Schmidt

Flüsse finden sich überall - beim Berechnen der maximal führbaren Wassermenge durch Rohr- und Kanalsystem, beim Aufrunden von demographischen Daten oder auch für die Berechnung des nächsten Aushebungsschachtes im Bergbau über Tage.

In dieser Masterarbeit sollenAlgorithmen zur Berechnung von maximalen Flüssen implementiert werden, die skalieren und in der Rechenzeit kompetitiv mit den heutzutage schnellsten vorhandenen state-of-the-art Lösungen ist. Als neuer Ansatz sollen dabei strukturelle Einsichten in maximal adjacency orderings benutzt werden, um den Geschwindigkeitsvorteil zu erreichen. Diese Masterarbeit benötigt daher

  • Expertise in C++,
  • die Fähigkeit, effizienten C++-Code für Algorithmen und die unterliegende Graphendatenstruktur zu schreiben,
  • Kenntnisse von Graphen und Interesse an Graphentheorie und Algorithmen.

Die Ergebnisse dieser Implementierung sollen quelloffen und plattformübergreifend zur Verfügung gestellt werden. Bei Interesse an dieser Arbeit kontaktieren Sie mich bitte per Email.