Netzwerkflussspanner
| Vortragende(r): |
| Dr. Knut Odermann |
| Inhalt: |
| 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. |
| Zeiten: |
| Dienstag, der 28.06.2011, 16:45 - 17:15 Uhr, Raum 1/219 |
