# An Accelerated Maximum Flow Algorithm with Prediction Enhancement in Dynamic LEO Networks
###### Abstract
By leveraging historical data and predictive modeling, these approaches aim to warm-start flow calculations [9], reducing the need for costly recalculations as the network evolves. Reinforcement learning has also been explored to optimize data transmission in LEO networks, particularly for congestion control and efficient routing [10]. Inspired by these approaches, this paper introduces a novel accelerated maximum flow algorithm specifically tailored to the unique challenges of dynamic LEO networks with high data throughput requirements. The proposed approach combines a predictive warm-start mechanism with an extended application of the energy-time expanded graph (e-TEG) model [11], offering a solution that operates efficiently under the dual constraints of dynamic topologies and  
Figure 1: A demo example of an observation satellite transmitting data to an Earth ground station via relay satellites in a LEO constellation. limited processing capability of satellites. Unlike traditional maximum flow algorithms that require recalculations with each network change, our method begins with a predictive warm-start informed by past and anticipated network states, minimizing computational demands and allowing rapid response to network shifts without recalculating from scratch. In addition to predictive warm-starting, we incorporate a learning-augmented component that adapts flow estimations based on historical network patterns. Machine learning techniques, including graph embedding-based reinforcement learning, have recently been explored to optimize routing and path selection in large-scale LEO networks [12]. Inspired by these advancements, our approach leverages historical network behavior to enhance flow predictions, further reducing the need for recalculations and improving computational efficiency. The combination of predictive initialization, e-TEG modeling, and learning-augmented adaptability forms a high-performance framework for data-intensive applications in LEO networks. The main contributions of this paper are summarized as follows:  
1. We introduce a novel predictive warm-start approach for maximum flow calculations in dynamic LEO networks. The method uses prior and anticipated network states to initialize the algorithm closer to optimal solutions, significantly reducing computation time. 2. The proposed algorithm incorporates a learning-augmented component that uses historical network patterns to inform flow predictions. This feature allows the algorithm to dynamically adjust to network shifts with minimal recalculations, enhancing its robustness and efficiency in environments with frequent connectivity changes. 3. We provide a theoretical analysis of the predictive flow algorithm's feasibility and computational efficiency, supported by extensive empirical validation. Experimental results confirm the algorithm's robustness and effectiveness across varied network and hardware conditions in LEO environments. The remainder of this paper is organized as follows. Section 2 reviews the related work on maximum flow computation in LEO satellite networks and the application of predictive techniques to enhance the Ford-Fulkerson algorithm. Section 3 describes the system model and formulates the maximum flow problem in LEO networks. Section 4 details the proposed prediction algorithm designed for LEO networks and the warm-start Ford-Fulkerson accelerated algorithm. Section 5 validates the performance of both algorithms through extensive evaluations. Finally, Section 6 concludes this work and discusses potential research directions.