# An Accelerated Maximum Flow Algorithm with Prediction Enhancement in Dynamic LEO Networks
## 4 Predictive Acceleration Algorithm for e-TEG Satellite Networks
### Residual Network Update  
In this subsection, we describe the process of updating the e-TEG network to account for the dynamic evolution of its topology as shown in Algorithm 2.  
```
0: Newly added network \(G^{\prime}(\mathcal{V}^{\prime},\mathcal{A}^{\prime})\), residual network \(G(\mathcal{V},\mathcal{A})\)
1:\(\mathcal{V}^{*}\leftarrow\mathcal{V}\cup\mathcal{V}^{\prime}\) [Merge node sets from old and new networks]
2:for each \((\mu,\
u)\in\mathcal{A}^{\prime}\)do
3:\(\mathcal{A}^{*}\leftarrow\mathcal{A}\cup\{(\mu,\
u)\}\) [Integrate new edges into residual network]
4:if\(c^{\prime}(\mu,\
u)>0\)then
5:\(c^{*}(\mu,\
u)=c^{\prime}(\mu,\
u)\) [Update capacity for active edges]
6:endif
7:endfor
8: For the observation satellite \(s_{1}\), \(c^{\prime}(s_{1},s_{1}^{{}^{\prime}})\leftarrow+\infty\) [Set infinite capacity for observation links]
9: For the ground station \(g_{1}\), \(c^{\prime}(g_{1},g_{1}^{{}^{\prime}})\leftarrow+\infty\) [Ensure unbounded downlink capacity]
10:for\(\mu\in\) all LEO satellites do
11:\(c^{\prime}(\mu,\mu^{\prime})\leftarrow\mathcal{E}_{\mu}\) [Assign energy-constrained capacity using \(\mathcal{E}_{\mu}\)]
12:endfor
13:return Updated residual network \(G^{*}(\mathcal{V}^{*},\mathcal{A}^{*})\)
```  
**Algorithm 2** Residual network update based on the e-TEG network.  
In Algorithm 2, we construct a time-unfolding graph \(G(\mathcal{V},\mathcal{A})\) to represent the e-TEG network from the initial time interval \(\tau_{1}\) to the \(i\)-th time interval \(\tau_{i}\). When the network expands into a new time interval, denoted as \(\tau_{i+1}\), we construct a novel snapshot graph and transform it into an e-TEG network, represented as \(G^{\prime}(\mathcal{V}^{\prime},\mathcal{A}^{\prime})\). This snapshot graph captures the current state of the network at \(\tau_{i+1}\), which includes newly introduced nodes, edges, and transmission paths. We then integrate this new snapshot graph into the existing time-unfolding graph to form an updated time-unfolding graph \(G^{*}(\mathcal{V}^{*},\mathcal{A}^{*})\), where in Step 1, \(\mathcal{V}^{*}=\mathcal{V}\cup\mathcal{V}^{\prime}\); in Step 3, \(\mathcal{A}^{*}=\mathcal{A}\cup\mathcal{A}^{\prime}\); and in Step 5, the capacity of each edge is updated. This process ensures that the evolving network topology is accurately captured and represented in the time-unfolding graph.  
_Complexity analysis_: The proposed update process leverages the continuity of the time-unfolding graph, eliminating the need to reinitialize the network from scratch. Instead, the algorithm incrementally integrates the newly added components into the residual network from the previous interval. This approach significantly reduces computational overhead compared to traditional methods.  
The time complexity of the update process is determined by the size of the newly added network components. Specifically, adding new edges requires \(O(E^{\prime})\), where \(E^{\prime}\) is the number of edges in the newly added network, adding new vertices requires \(O(N^{\prime})\), where \(N^{\prime}\) is the number of vertices in the newly added network, and updating capacities requires \(O(E^{\prime})\), as edge capacities are modified based on the new snapshot. Thus, the overall time complexity for updating the network is \(O(E^{\prime}+N^{\prime})\). This incremental update approach is considerably more efficient than traditional methods, which require reinitializing the entire network for every update. As a result, the algorithm is well-suited for dynamic e-TEG networks, where frequent topology changes must be handled efficiently.