Prof. Dr. R. Laue                                                                            WS0001
                                Graphentheoretische Optimierung
                                Übungsblatt 10
                                Abgabe: 12.1 vor der Vorlesung

URL:         /axel/graph_ws0001_blatt8.html
 
 
 

Aufgabe 20 Blocking Flow - (4+4 Punkte)

In der Vorlesung wurde das Verfahren von Malhotra,Kumar, Mahaswari  zur Berechnung eines 'blocking flow'  mit Aufwand O(|V|2) vorgestellt.
1) Formulieren Sie es als Algorithmus in Pseudocode.
2) Berechnen Sie einen blockierenden Fluss für folgendes geschichtete Netzwerk (aus Syslo,Deo, Kowalik)