Multi-commodity flow problems concern with the transshipment of more than one commodities from respective sources to the corresponding sinks without violating the capacity constraints on the arcs. If the objective of the problem is to send the maximum amount of flow within given time horizon, then it becomes the maximum flow problem. In multi-commodity flow problem, flow of different commodities departing from their sources arrive at the common intermediate node and have to share the capacity through the arc. The sharing of the capacity in the common arc (bundle arc) is one of the major issues in the multi-commodity flow problems. In this paper, we introduce the maximum static and maximum dynamic multi-commodity flow problems with proportional capacity sharing and present polynomial time algorithms to solve the problems. Similarly, we investigate the maximum dynamic multi-commodity flow problem with flow-dependent capacity sharing and present a pseudo-polynomial time solution strategy.
Previous Article in event
Previous Article in session
Next Article in event
Next Article in session
Maximum Multi-Commodity Flow with Proportional and Flow-dependent Capacity Sharing
Published:
26 September 2021
by MDPI
in The 1st Online Conference on Algorithms
session Combinatorial Optimization, Graph and Network Algorithms
Abstract:
Keywords: Multi-commodity, maximum flow, proportional capacity sharing, flow-dependent capacity sharing.