# An Accelerated Maximum Flow Algorithm with Prediction Enhancement in Dynamic LEO Networks
###### Abstract  
Efficient data transmission in low Earth orbit (LEO) satellite networks is critical for supporting real-time global communication, Earth observation, and numerous data-intensive space missions. A fundamental challenge in these networks involves solving the maximum flow problem, which determines the optimal data throughput across highly dynamic topologies with limited onboard energy and data processing capability. Traditional algorithms often fall short in these environments due to their high computational costs and inability to adapt to frequent topological changes or fluctuating link capacities. This paper introduces an accelerated maximum flow algorithm specifically designed for dynamic LEO networks, leveraging a prediction-enhanced approach to improve both speed and adaptability. The proposed algorithm integrates a novel energy-time expanded graph (e-TEG) framework, which jointly models satellite-specific constraints including time-varying inter-satellite visibility, limited onboard processing capacities, and dynamic link capacities. In addition, a learning-augmented warm-start strategy is introduced to enhance the Ford-Fulkerson algorithm. It generates near-optimal initial flows based on historical network states, which reduces the number of augmentation steps required and accelerates computation under dynamic conditions. Theoretical analyses confirm the correctness and time efficiency of the proposed approach. Evaluation results validate that the prediction-enhanced approach achieves up to a 32.2% reduction in computation time compared to conventional methods, particularly under varying storage capacity and network topologies. These results demonstrate the algorithm's potential to support high-throughput, efficient data transmission in future satellite communication systems. s 2025 2025 2025 2025 2025 2025 2025 2025 2  
A fundamental challenge in LEO networks is efficiently handling these large-scale, dynamic data flows. Satellites move rapidly, resulting in frequent changes in connectivity between nodes and ground stations. The connectivity properties of large-scale LEO constellations have been recently analyzed using percolation theory [6], providing insights into how network topology influences communication reliability and data flow. Additionally, limited onboard data processing capability and fluctuating link capacities impose further constraints on optimizing data flow. At the core of this challenge is the maximum flow problem, a classic network optimization problem that seeks to maximize data throughput from source nodes to destination nodes across a network. Solving this problem efficiently is essential for sustaining real-time data delivery in large-scale satellite systems. To illustrate, consider a representative scenario that involves an observation satellite transmitting data to a distant ground station. Due to movement in the constellation, the transmission path often includes multiple intermediate relay satellites. Figure 1 shows a simplified example of data flow; the observation satellite (node \(s\)) transmits data to the ground station (node \(g\)) through relay satellites (nodes \(v_{1}\) and \(v_{2}\)) along two different paths, \(s-v_{1}-g\) and \(s-v_{2}-g\). Each link has limited capacity, and as satellites move, connectivity changes, requiring frequent recomputation of the optimal data path. In this scenario, the maximum flow problem involves calculating the highest data throughput from \(s\) to \(g\) across all available paths. In static networks, maximum flow calculations can often be handled with traditional algorithms like Ford-Fulkerson [7] or Dinic's [8]. However, in LEO networks, every topological change, whether due to orbital motion, link failure, or energy constraints, leads to a full recomputation, limiting responsiveness in real-time applications. To address these limitations, recent research has turned to predictive and adaptive techniques for optimizing maximum flow calculations.