Generalized Maximum Flow with Excess Storage on Series Parallel Lossy Networks
摘要
The concept of excess storage has gained the remarkable focus in the process of flow maximization in the recent days. In the classical networks, it is assumed that flow remains constant when it passes from one end of an arc to the other end and inflow into the intermediate nodes equals outflow. When the first assumption is not valid and results in a numerically smaller value, the network is said to be lossy. Similarly, when the second assumption is not valid, there is possibility to gain the additional flow from the source node, provided, the intermediate nodes are equipped with storage capacity. This additional flow can be stored into the intermediate nodes in a specific order to increase the total amount of flow outgoing from the source node significantly. We introduce the generalized maximum static and the earliest arrival flow problems with excess storage in two terminal series parallel lossy networks, where loss should be defined depending upon the scenarios. For the solution of these problems, we present efficient algorithms. Excess storage is made following the distance-based priority order of the intermediate nodes. The effectiveness is supported by numerical computation.