# An Accelerated Maximum Flow Algorithm with Prediction Enhancement in Dynamic LEO Networks
## 3 System Model and Problem Formulation
### Update Mechanism of the Residual Network  
To efficiently compute maximum flow in a dynamic LEO satellite network, the residual network must be continuously updated to reflect changes in network topology and resource constraints [36]. As the time horizon progresses, the network evolves, with new communication links emerging, existing links vanishing, or resource capacities fluctuating. To account for these changes, we employ a residual network update mechanism integrated with the e-TEG framework. This mechanism allows for the dynamic expansion and adjustment of the network model, ensuring that maximum flow computations remain valid and up-to-date.  
Initially, the e-TEG is constructed based on the network's state during the first time slot \(\tau_{1}\). This initial representation serves as the starting residual network, encapsulating the residual capacities of nodes and edges. As the solving process progresses, the e-TEG is incrementally expanded by incorporating new snapshots of the network corresponding to subsequent time slots \(\{\tau_{2},\tau_{3},\ldots,\tau_{k}\}\). For each time slot \(\tau_{i}\), the residual network is updated to reflect the current state of the network, including changes in node and edge capacities.  
To achieve this, a snapshot graph \(G^{\prime}_{i}=(\mathcal{V}^{\prime}_{i^{\prime}},\mathcal{A}^{\prime}_{i})\) is constructed for each time slot \(\tau_{i}\), capturing all nodes, edges, and their associated capacities during that interval. The snapshot graph is then integrated into the existing e-TEG to form the updated graph \(G_{i}=(\mathcal{V}^{*}_{i},\mathcal{A}^{*}_{i})\), where we have the following:  
\[\mathcal{V}^{*}_{i}=\mathcal{V}^{*}_{i-1}\cup\mathcal{V}^{\prime}_{i},\quad \mathcal{A}^{*}_{i}=\mathcal{A}^{*}_{i-1}\cup\mathcal{A}^{\prime}_{i} \tag{13}\]  
This process ensures that the e-TEG evolves to represent the network's state from \(\tau_{1}\) to \(\tau_{i}\).  
During the update process, the capacities of edges in the residual network are adjusted to reflect the flow already transmitted and the newly available capacities. For an edge \((\hat{v}^{h}_{i},\hat{v}^{h}_{j})\in\mathcal{A}^{*}\), the updated capacity \(C^{\prime}_{\hat{v}^{h}_{i},\hat{v}^{h}_{j}}\) is given by the following:  
\[C^{\prime}_{\hat{v}^{h}_{i},\hat{v}^{h}_{j}}=C_{\hat{v}^{h}_{i},\hat{v}^{h}_{ j}}+F_{\hat{v}^{h}_{i},\hat{v}^{h}_{j}} \tag{14}\]  
Figure 3: e-TEG model based on one source satellite, two LEO satellites, and one ground station.  
where \(C_{\phi_{i}^{h},\phi_{j}^{h}}\) is the original capacity of the edge, and \(F_{\phi_{i}^{h},\phi_{j}^{h}}\) represents the flow added to the edge during the current time slot.  
Figure 4 illustrates this update mechanism. The figure shows the residual network at a given time slot, the newly added snapshot graph for the next time slot, and how the two are merged to form the updated e-TEG. This process ensures that the residual network accurately reflects the current topology, resource capacities, and flow conditions of the LEO satellite network.