Multiterminal network flows and applications

The paper discusses the ways to use the condensation technique of Gomory/Hu in the case of non-symmetric networks. Sufficient conditions to get the value of a maximal flow as row resp. column sum of the capacity matrix are derived. Procedures to determine the cut with minimal capacity are developed and applications of the minimal cut technique to problems of optimal sequencing are given.

---

Zusammenfassung Das Papier diskutiert die Möglichkeiten, die Kondensationstechnik von Gomory/Hu auf den Fall unsymmetrischer Netzwerke zu übertragen. Es werden hinreichende Bedingungen dafür abgeleitet, daß der Wert eines maximalen Flusses mit der Zeilenbzw. Spaltensumme der Kapazitätsmatrix übereinstimmt. Es werden Verfahren entwickelt, den Schnitt minimaler Kapazität zu bestimmen. Anwendungen der minimalen Schnitt-Technik auf Probleme der optimalen Reihenfolge werden vorgestellt.