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 |
