New methods for multi-commodity flows (Q920829): Difference between revisions

Most approaches to multi-commodity flows which are presently successful have used the ideas of linear programming. \textit{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.