zbMATH — the first resource for mathematics

Combinatorial approaches to multiflow problems. (English) Zbl 0598.90036
Let V be a finite set and denote by (V) and [V] the sets of all ordered and unordered pairs (x,y) and [x,y] (x,y\(\in V)\). A multiflow is a family \(F=\{f_ u| u\in U\}\) where \(U\subseteq [V]\) and for \(u=[s,t]\) \(f_ u\) is a flow with terminals s and t (i.e. either a flow from s to t or from t to s) in the complete directed graph \(G=(V,(V)).\)
Define \(\zeta_ F\), \(\delta_ F\in {\mathbb{R}}_+^{[V]}\) by \[ \zeta_ F[x,y]=\sum \{f(x,y)+f(y,x)| f\in F\}\quad and \] \[ \delta_ F[x,y]=\| f_{[x,y]}\|,\quad if\quad [x,y]\in U,\quad and\quad \delta_ F[x,y]=0,\quad otherwise \] where \(\| f\|\) denotes the value of flow f. The author discusses theoretical properties of the following two problems. (a) The feasibility problem: Given \(c,d\in {\mathbb{R}}_+^{[V]}\), find a multiflow F satisfying (1) \(\zeta_ F\leq c\) and \(\delta_ F\geq d\). (b) A general extremal multiflow problem: Given \(a,b,c,d\in {\mathbb{R}}_+^{[V]}\), find a multiflow F maximizing \(a\delta_ F-b\zeta_ F\) subject to (1).
Deriving these results a ’combinatorial’ approach is used rather than a ’linear programming’ approach.
Reviewer: P.Bruckner

90B10 Deterministic network models in operations research
Full Text: DOI
[1] Ford, L.R.; Fulkerson, D.R., Flows in networks, (1962), Princeton Univ. Press Princeton, NJ · Zbl 0139.13701
[2] Hu, T.C., Integer programming and network flows, (1970), Addison-Wesley Reading, MA · Zbl 0197.45701
[3] Cherkasski, B.V., Solution for a problem on multicommodity network flows, Ekonomika i matem. metody, 13, 1, 143-151, (1977), (Russian)
[4] Cherkasski, B.V., On multiterminal multicommodity flow problems, (), 261-286, (Russian)
[5] Adelson-Velski, G.M.; Dinic, E.A.; Karzanov, A.V., Algorithms for flows in networks, (1975), Nauka Moscow, (Russian)
[6] Onaga, K.; Kakusho, O., On feasibility conditions of multicommodity flows in networks, IEEE trans. circuit theory, 18, 4, 425-429, (1971)
[7] Iri, M., On an extension of the maximum-flow minimum-cut theorem to multicommodity flows, J. oper. res. soc. Japan, 13, 129-135, (1971) · Zbl 0223.90010
[8] B.A. Papernov, On existence of multicommodity flows, in: “Issledovaniya po Discretnoy Optimizacii“ (Moscow, “Nauka”) 230-261 (Russian).
[9] Assad, A.A., Multicommodity network flows — A survey, Networks, 8, 1, 37-91, (1978) · Zbl 0381.90040
[10] Lomonosov, M.V., On flows in networks, Problemy peredatchi informacii, 14, 4, 60-73, (1978), (Russian) · Zbl 0423.05016
[11] M.V. Lomonosov, Solutions for two problems on flows in networks, to appear (submitted to the same journal in July 1976, Russian).
[12] Karzanov, A.V., Combinatorial techniques for cut-dependent multiflow problems, (), 6-70, (Russian)
[13] Karzanov, A.V.; Poevzner, P.A., Characterization of the class of non-cut-dependent multiflow optimization problems, (), 70-81, (Russian)
[14] Karzanov, A.V., Time saving techniques for solving two known multiflow problems in undirected networks, (), 96-103, (Russian)
[15] Karzanov, A.V., On the cost minimization problem for maximal multiflows, (), 138-156, (Russian)
[16] Dinic, A.V.; Karzanov, A.E., On the existence of two integer-valued flows of unit magnitude, (), 127-137, (Russian)
[17] Kuperschtoch, V.L., On a generalization of the Ford-fulkerson theorem to multiterminal networks, Kiev kybernetika, 3, (1971), (Russian)
[18] Avis, D., Extremal metrics induced by graphs, (), 217-220 · Zbl 0469.05042
[19] Avis, D., On the extreme rays of the metric cone, Canad. J. math., 32, 1, 126-144, (1980) · Zbl 0468.05049
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.