Entwurf und Implementierung effizienter Verfahren für balancierte Flußprobleme und allgemeine Matchingprobleme

• Applicant: Professor Dr. Dieter Jungnickel
• Subject Area: Mathematics
• Term: from 1998 to 2002
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 5153382

Die Codierung der ungewichteten Verfahren für Matching- und balancierte Flußprobleme ist weitgehend abgeschlossen. Dieser Code ist eingehend getestet und als Matching-Solver im Internet zugänglich. Die zugrundeliegende C++Bibliothek GOBLIN bedarf noch einer ausführlichen Dokumentation, um die Methoden für eine direkte Verwendung ohne Dateischnittstelle und die Quelltexte für zukünftige Projekte verfügbar zu machen. Die Theorie zu den ungewichteten Problemen, die Dualitätstheorie, sowie die polyedrische Beschreibung von balancierten Flüssen ist veröffentlicht bzw. veröffentlichungsreif. Algorithmen für gewichtete Probleme sind in der Reichweite dieses Projektes. Mit zwei oder drei Veröffentlichungen zu den Themen Primal-Dual-Verfahren und Primale Verfahren könnte das Gebiet der balancierten Flußprobleme inhaltlich abgeschlossen werden. Mit dem entsprechenden Quell-Code wird GOBLIN vermutlich zur umfangreichsten und leistungsfähigsten frei verfügbaren Bibliothek für Probleme der Netzwerk-Programmierung.

• DFG Programme: Research Grants