Open AccessA Review of Flow-Capacitated Networks: Algorithms, Techniques and Applications
Author(s) -
Omar Mutab Alsalami,
Ali Muhammad Ali Rushdi
Publication year - 2021
Publication title -
asian journal of research in computer science
Language(s) - English
Resource type - Journals
ISSN - 2581-8260
DOI - 10.9734/ajrcos/2021/v7i330179
Subject(s) - computer science , flow network , terminology , decomposition , maximum flow problem , flow (mathematics) , algorithm , graph rewriting , graph , transformation (genetics) , theoretical computer science , mathematical proof , reduction (mathematics) , mathematical optimization , graph theory , mathematics , ecology , philosophy , linguistics , geometry , combinatorics , biology , biochemistry , chemistry , gene
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.