Article Preview
TopIntroducion
The maximum flow problem is a network-based problem, whose objective is to determine the maximum amount of units that can pass through a network. All links in the network have capacity restrictions. Given a network with given capacity restrictions on each link, the maximum flow problem usually deals with the determination of flow patterns thorough various links in the network, so that a maximum flow can arrive at a specified node known as the “destination node” from another specified node, known as the “origin,” where the supply in unlimited. Ahmed et al. (2013), Kaml (2017), Munapo et al. (2021), Sarukhi et al. (2017), and Yuan et al. (2010), among others, tackled this problem. The maximum flow network can be directed or non-directed; water networks and road networks are examples of nondirected and directed networks, respectively.
The maximum flow problem has many applications, which include maximizing movement of water from dams, rivers, and boreholes to treatment sites, and then from treatment sites to residents. The maximum flow problem can be used to determine congestion points in urban road networks that require road expansion, so as to minimize congestion and delays. Also, the maximum flow problem is one of the network-based combinatorial optimization problems that requires the development of algorithms and heuristics to determine the maximum flow value in any given network. Researchers have been developing methods to solve maximum flow problems using concepts based on augmenting path, maximum flow – minimum cut theorem, and residual networks, among others.
Motivation
The various applications and the complexity of the maximum flow problem have motivated this research. The minimum cut theorem is very powerful and helps to determine the maximum flow value in any given network. The drawback is that it consumes time to determine all the cuts in the network and evaluate them to determine the minimum cut in the set of all possible cuts. Making the position of the minimum cut deterministic in any given network has motivated this research. It becomes very easy to determine the maximum flow value in any given network when the minimum cut position is deterministic. Most algorithms use augmenting paths to determine the maximum flow value in a network; however, in this research, the authors exploited other directions to avoid the use of augmenting paths and residual network concepts.
This research has the following contributions:
- 1.
The authors developed a new algorithm that is based on the concepts of maximum flow – minimum cut theorem. The design of the algorithm is simple; thus, it can be used for teaching purposes and without the aid of computer software.
- 2.
The authors proposed table-based maximum flow algorithm concepts, thus avoiding the augmenting paths and residual networks. The literature revealed that most of the existing algorithms are based on augmenting paths and residual network concepts.
- 3.
The authors proposed two theorems based on the max-flow min-cut theorem. These theorems are very useful in making the position of the minimum cut in any given network deterministic. The authors also proved their proposed theorems mathematically using max-flow min-cut theorem concepts.
This paper is organized in seven sections. The second section presents the literature related to the maximum flow problem; the third section presents the proposed algorithm and theorems, definitions of related terms, and notations; the fourth section offers numerical results and discussions; The fifth and sixth sections report the worst case time complexity of the algorithm and computational results, respectively; lastly, the seventh section provides the conclusion and further research suggestions.