Improved parallel algorithm for finding minimum cuts in stochastic flow networks

Abstract

The expansion of information in social networks, bioinformatics, and transportation has resulted in the emergence of enormous graphs with millions or even billions of nodes and edges. Examples include communication networks with stochastic bandwidth, traffic systems with probabilistic congestion, and power grids with uncertain load demand. These scenarios pose unique computational challenges due to their probabilistic nature and dynamic structure. Traditional sequential techniques for identifying minimum cuts in graphs are ineffective in this context, as their time complexity becomes excessively high. This thesis addresses the problem by employing parallel techniques to compute minimum cuts more efficiently on large-scale graphs, leveraging modern parallel computing resources without compromising accuracy. The initial investigation explores state-of-the-art algorithms such as Parallel Push-Relabel and Parallel Karger, which depend on specific hardware and software conditions. The results support the design of the Dynamic Parallel Graph Cuts Algorithm (DPGCA), while also identifying limitations such as inefficient memory usage, limited energy scalability, and poor resource distribution in current parallel implementations.