Complexity results for multicriterial and parametric network flows using a pathological graph of Zadeh

For two classes of network flow problems a worst-case analysis is given depending on the number of vertices of a pathological graph of Zadeh. Firstly, an exponential number of breakpoints in the optimal value function of the maximal flow problem in generalized networks with parametric capacities is demonstrated. Secondly, it is shown that the bicriterial min-cost flow has, in the worst case. an exponential number of efficient extreme point solutions in the objective space.

---

Zusammenfassung Für zwei Klassen von Netzwerkflußproblemen wird eine worst-case Analyse in Abhängigkeit von der Anzahl der Knoten eines pathologischen Graphen von Zadeh vorgenommen. Demnach besitzt das Maximalflußproblem in verallgemeinerten Netzwerken mit parametrischen Kapazitätsbeschränkungen eine exponentielle Anzahl von Knickstellen in der Optimalwertfunktion. und kostenminimale Flüsse haben bereits für zwei Kriterien eine exponentielle Zahl von effizienten Eckpunkten im Bildbereich.