zbMATH — the first resource for mathematics

New methods for multi-commodity flows. (English) Zbl 0708.90024
Most approaches to multi-commodity flows which are presently successful have used the ideas of linear programming. M. V. Lomonosov [Discrete Appl. Math. 11, 1-93 (1985; Zbl 0598.90036)] has reported on work by himself and his colleageus which seems to the present authors to offer promising aspects in generalizing existing graph theory based methodologies to the multi-commodity case.
In this paper the authors describe some of the theoretical work of Lomonosov and show how it may be implemented to provide an extremely efficient and practical algorithm for solving certain multi-commodity flow problems. Also described is an example of a network problem solved by this method. Finally, the authors discuss future developments.
Reviewer: E.Ciurea

90B10 Deterministic network models in operations research
90-08 Computational methods for problems pertaining to operations research and mathematical programming
Full Text: DOI
[1] Assad, A.A., Multicommodity network flows—a survey, Networks, 8, 37-91, (1978) · Zbl 0381.90040
[2] Gondran, M.; Minoux, M., Graphs and algorithms, (1984), Wiley New York · Zbl 1117.06010
[3] Lomonosov, M.V., Combinatorial approaches to multiflow problems, Discr. appl. math., 11, 1, 1-93, (1985) · Zbl 0598.90036
[4] Ford, L.R.; Fulkerson, D.R., Flows in networks, (1962), Princeton Univ. Press Princeton, N.J. · Zbl 0139.13701
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.