2010/01/05 by Dhananjay P. Mehendale, Mehendale, Dhananjay P.
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Algorithm #Combinatorics #FOS: Mathematics #Flow (mathematics) #Flow network #General Mathematics (math.GM) #Geometry #Graph Theory and Algorithms #Mathematical optimization #Mathematics #Maximum flow problem #Minimum-cost flow problem #Multi-commodity flow problem #Sink (geography) #VLSI and FPGA Design Techniques #math.GM
paper · pdf · doi:10.48550/arxiv.1001.0629
published in arXiv (Cornell University) (Cornell University) · 11 pages. Typos are corrected
openalex publication_date 2010/01/05 · arxiv created 2010/01/13 · arxiv updated 2010/01/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We propose a new algorithm to obtain max flow for the multicommodity flow. This algorithm utilizes the max-flow min-cut theorem and the well known labeling algorithm due to Ford and Fulkerson [1]. We proceed as follows: We select one source/sink pair among the n distinguished source/sink pairs at a time and treat the given multicommodity network as a single commodity network for such chosen source/sink pair. Then applying standard labeling algorithm, separately for each sink/source pair, the feasible flow which is max flow and the corresponding minimum cut corresponding to each source/sink pair is obtained. A record is made of these cuts and the paths flowing through the edges of these cuts. This record is then utilized to develop our algorithm to obtain max flow for multicommodity flow. In this paper we have pinpointed the difficulty behind not getting a max flow min cut type theorem for multicommodity flow and found out a remedy.