Skip to content
Research Article Open access CC BY 4.0

A Review of Flow-Capacitated Networks: Algorithms, Techniques and Applications

Omar Mutab Alsalami, Ali Muhammad Ali Rushdi

Asian Journal of Research in Computer Science · pp. 1–33 · Published 19 Mar 2021

10.9734/ajrcos/2021/v7i330179

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.

Capacitated networks max-flow min-cut theorem Ford and Fulkerson algorithm reduction and transformation techniques decomposition technique flow network applications.

References (52)

  1. 1 Flows in networks
  2. 2 Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems [DOI]
  3. 3 Algorithm Design
  4. 4 Efficient identification of Web communities [DOI]
  5. 5 Graphs: Theory and Algorithms [DOI]
  6. 6 Graphs, Networks and Algorithms [DOI]
  7. 7 Interactive Graph Cut Based Segmentation with Shape Priors [DOI]
  8. 8 Max flows in O(nm) time, or better [DOI]
  9. 9 The Pseudoflow Algorithm: A New Algorithm for the Maximum-Flow Problem [DOI]
  10. 10 Electronic Design Automation: Synthesis, Verification, and Test
  11. 11 Fusion of probabilistic A* algorithm and fuzzy inference system for robotic path planning [DOI]
  12. 12 Dinitz’ Algorithm: The Original Version and Even’s Version [DOI]
  13. 13 A Computational Study of the Pseudoflow and Push-Relabel Algorithms for the Maximum Flow Problem [DOI]
  14. 14 A generalization of Dijkstra's shortest path algorithm with applications to VLSI routing [DOI]
  15. 15 Topology cuts: A novel min-cut/max-flow algorithm for topology preserving segmentation in N–D images [DOI]
  16. 16 Complexity analysis for maximum flow problems with arc reversals [DOI]
  17. 17 Risk-Based Reliability Analysis and Generic Principles for Risk Reduction [DOI]
  18. 18 Solving the bicriterion routing and scheduling problem for hazardous materials distribution [DOI]
  19. 19 Identifying geographically diverse routes for the transportation of hazardous materials [DOI]
  20. 20 Shortest path based simulated annealing algorithm for dynamic facility layout problem under dynamic business environment [DOI]
  21. 21 New Trends in System Reliability Evaluation [DOI]
  22. 22 The Pseudoflow Algorithm and the Pseudoflow-Based Simplex for the Maximum Flow Problem [DOI]
  23. 23 Computing shortest paths for transportation of hazardous materials in continuous spaces [DOI]
  24. 24 Graph Search with Appearance and Shape Information for 3-D Prostate and Bladder Segmentation [DOI]
  25. 25 A specialized network simplex algorithm for the constrained maximum flow problem [DOI]
  26. 26 On Reliability Evaluation by Network Decomposition [DOI]
  27. 27 Fuzzy graphs modelling for HazMat telegeomonitoring [DOI]
  28. 28 Interference aware resource allocation for hybrid hierarchical wireless networks [DOI]
  29. 29 Reliability Evaluation by Network Decomposition [DOI]
  30. 30 The Use of Wye-Delta Transformations in Network Simplification [DOI]
  31. 31 Node-Disjoint Paths on the Mesh and a New Trade-Off in VLSI Layout [DOI]
  32. 32 A hardware-efficient scheme and FPGA realization for computation of single pair shortest path for a mobile automaton [DOI]
  33. 33 Finding web communities by maximum flow algorithm using well assigned edge capacities
  34. 34 The K-Connection Location Problem in a Plane [DOI]
  35. 35 Maximum bipartite flow in networks with adaptive channel width [DOI]
  36. 36 Application of the Maximum Flow Problem to Sensor Placement on Urban Road Networks for Homeland Security
  37. 37 Transfinite Ford–Fulkerson on a finite network [DOI]
  38. 38 An Effective Algorithm of Shortest Path Planning in a Static Environment [DOI]
  39. 39 A Tutorial Exposition of Various Methods for Analyzing Capacitated Networks [DOI]
  40. 40 Extracting Research Communities by Improved Maximum Flow Algorithm [DOI]
  41. 41 Checking Correctness of a Symbolic Reliability Expression for a Capacitated Network [DOI]
  42. 42 Mining Communities on the Web Using a Max-Flow and a Site-Oriented Framework [DOI]
  43. 43 Analysing Weighted Networks: An Approach via Maximum Flows [DOI]
  44. 44 Locally minimal uniformly oriented shortest networks [DOI]
  45. 45 Network reliability evaluation by decomposition [DOI]
  46. 46 Star-delta transformations of bidirectional branches in probabilistic flow networks [DOI]
  47. 47 Cross line and column generation for the cut covering problem in wireless networks [DOI]
  48. 48 Techniques for Analyzing Capacitated Networks: A Tutorial Review [DOI]
  49. 49 Indexes of a telecommunication network [DOI]
  50. 50 Flow Networks: Analysis and optimization of repairable flow networks, networks with disturbed flows, static flow networks and reliability networks
  51. 51 Introduction to Algorithms
  52. 52 PROBABILITY AND STATISTICS

Cited by 5

Cooperative TU-games: Dominance, stable sets, and the core revisited

Begoña Subiza, José-Manuel Giménez-Gómez, Josep E. Peris · Journal of Mathematical Economics · 2025

Cooperative Tu-Games: Dominance, Stable Sets, and the Core Revisited

José-Manuel Giménez-Gómez, Begoña Subiza, Josep E. Peris · 2024

Showing 2 of 5 known citations — external sources report more than can currently be individually listed.

Related research

Article metrics

Real usage data collected on this platform.

19

Page views

0

PDF downloads

2

Outbound clicks

5

Citations

Views over time

Views by country

Approximate, from request IP at view time — not citizenship or institution. Countries with fewer than 5 views are grouped as "Other".

Traffic sources

Referring site, by host.

Views and downloads exclude known bots/crawlers. Citations combines this platform's own DOI-resolved index with each external source's own reported total — see Cited by above for individually listed citing works. Last refreshed 0 seconds ago.