Design, Implementierung und Evaluierung von Netzwerkdatenstrukturen und Netzwerkalgorithmen zum Lösen des Minimum-Cost Flow Problems

Die Idee Software nur einmal zu entwickeln, um sie dann vielseitig einzusetzen, ist seit langer Zeit die treibende Kraft im Software Engineering. Diese Arbeit widmet sich der Fragestellung, ob es mit modernen Methoden des Software Engineerings möglich ist, bei der Entwicklung einer Softwarebibliothek den häufig auftretenden Konfikt zwischen Effizienz und Flexibilität aufzulösen. Mit dem Design, der Implementierung und der Evaluierung von Netzwerkdatenstrukturen und Netzwerkalgorithmen zum Lösen des Minimum-Cost Flow Problems (MCF-Problem) geben wir eine positive Antwort. Im ersten Teil der Arbeit werden zunächst mehrere Lösungsansätze für das MCF-Problem eingehend diskutiert. Anschließend wird das Design und die Implementierung einer generativen Softwarebibliothek zur Erzeugung von Graph- und Netzwerkdatenstrukturen durch einen C++ Compiler betrachtet. Die Implementierung einiger algorithmischer Ansätze für das MCF-Problem sowie deren Evaluierung hinsichtlich des Laufzeitverhaltens liefern wichtige Ergebnisse für die Entwicklung von Graph- und Netzwerkalgorithmen.