A Review of Flow-Capacitated Networks: Algorithms, Techniques and Applications
Omar Mutab Alsalami *
Department of Electrical Engineering, College of Engineering, Taif University, P.O. Box 11099, Taif 21944, Kingdom of Saudi Arabia.
Ali Muhammad Ali Rushdi
Department of Electrical and Computer Engineering, Faculty of Engineering, King Abdulaziz University, P. O. Box 80200, Jeddah, 21589, Kingdom of Saudi Arabia.
*Author to whom correspondence should be addressed.
Abstract
This paper presents a review of flow network concepts, including definition of some graph-theoretic basics and a discussion of network flow properties. It also provides an overview of some crucial algorithms used to solve the maximum-flow problem such as the Ford and Fulkerson algorithm (FFA), supplemented with alternative solutions, together with the essential terminology for this algorithm. Moreover, this paper explains the max-flow min-cut theorem in detail, analyzes the concepts behind it, and provides some examples and their solutions to demonstrate this theorem. As a bonus, it expounds the reduction and transformation techniques used in a capacitated network. In addition, this paper reviews one of the popular techniques for analyzing capacitated networks, which is the “decomposition technique”. This technique is centered on conditioning a complicated network on the possible states of a keystone element or on the possible combinations of states of many keystone elements. Some applications of capacitated network problems are addressed based on each type of problem being discussed.
Keywords: Capacitated networks, max-flow min-cut theorem, Ford and Fulkerson algorithm, reduction and transformation techniques, decomposition technique, flow network applications.