Network flow spanners
Talking persons: |
Dr. Knut Odermann |
Abstract: |
In der algorithmischen Graphentheorie sind bereits einige Probleme bekannt, bei denen es darum geht, zu einem gegebenen Netzwerk ein kostengünstiges Teilnetzwerk zu finden, in dem der maximale Fluss zwischen jedem Quelle-Senke-Paar möglichst groß ist. Im Vortrag werden sogenannte Netzwerkflussspanner vorgestellt. Es wird gezeigt, dass für Netzwerke, denen ein Graph mit einer Baumweite von höchstens $2$ zugrundeliegt, das Netzwerkflussspannerproblem für Einheitskapazitäten und Einheitskosten auf allen Kanten in polynomieller Zeit gelöst werden kann. |
Times: |
Tuesday 28th June 2011, 4.45 pm - 5.15 pm, room 1/219 |