An Accelerated Maximum Flow Algorithm with Prediction Enhancement in Dynamic LEO Networks

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.