Premium
Efficient algorithms for the maximum concurrent flow problem
Author(s) -
Bauguion PierreOlivier,
BenAmeur Walid,
Gourdin Eric
Publication year - 2015
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21572
Subject(s) - computer science , decomposition , shortest path problem , vertex (graph theory) , path (computing) , scheme (mathematics) , algorithm , flow (mathematics) , flow network , mathematical optimization , set (abstract data type) , tree (set theory) , computation , arc routing , linear programming , decomposition method (queueing theory) , mathematics , theoretical computer science , routing (electronic design automation) , discrete mathematics , combinatorics , graph , biology , programming language , ecology , mathematical analysis , computer network , geometry
In this article, we propose a generic decomposition scheme for the maximum concurrent flow problem. This decomposition scheme encompasses many models, including, among many others, the classical path formulation and the less studied tree formulation, where the flows of commodities sharing a same source vertex are routed on a set of trees. The pricing problem for this generic model is based on shortest‐path computations. We show that the tree‐based linear programming formulation can be solved much more quickly than the path or the aggregated arc‐flow formulation. Some other decomposition schemes can lead to even faster resolution times. Finally, an efficient strongly polynomial‐time combinatorial algorithm is proposed for the single‐source case. © 2014 Wiley Periodicals, Inc. NETWORKS, Vol. 65(1), 56–67. 2015