New methods for multi-commodity flows.

*(English)*Zbl 0708.90024Most 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.

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

##### MSC:

90B10 | Deterministic network models in operations research |

90-08 | Computational methods for problems pertaining to operations research and mathematical programming |

##### Keywords:

multi-commodity flows
PDF
BibTeX
XML
Cite

\textit{N. Boland} and \textit{A. I. Mees}, Comput. Math. Appl. 20, No. 1, 29--38 (1990; Zbl 0708.90024)

Full Text:
DOI

##### References:

[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.