# An Accelerated Maximum Flow Algorithm with Prediction Enhancement in Dynamic LEO Networks
## 4 Predictive Acceleration Algorithm for e-TEG Satellite Networks
### Acquisition of Predictive Flow  
Predictive flow is an informed estimate of the maximum flow for the current network state, derived from prior network configurations or heuristic approximations. The predictive flow enables a warm start for the algorithm, significantly reducing computational overhead. To compute predictive flow in an e-TEG network \(G=(\mathcal{V},\mathcal{A})\) for a given time slot \(\tau_{h}\), the algorithm identifies a feasible path from the source \(s_{1}^{h}\) to the ground station \(g_{1}^{h}\) while satisfying constraints in Equations (15) and (18) in Section 3. The predictive flow value \(\hat{f}\) is then initialized as the minimum capacity along the path. Figure 5 presents a demo example to illustrate an e-TEG satellite network operating within \((2+1)\) consecutive time slots. This network comprises a source satellite, two relay satellites, and a ground station, with the time dimension divided into original time slots \(\tau_{1}\) and \(\tau_{2}\), as well as an additional time slot \(\tau_{3}\). Since \(s_{1}\) can transmit at any time, \(\mathcal{C}_{s_{1}^{h},s_{1}^{h+1}}\) is set to infinity, ensuring the existence of a path from \(s_{1}^{1}\) to \(s_{1}^{h}\). Therefore, the task of computing a predictive flow from \(s_{1}^{1}\) to \(s_{1}^{h}\) reduces to finding the predictive flow from \(s_{1}^{h}\) to \(s_{1}^{h}\). To obtain the predictive flow for the e-TEG network for a given time slot, the algorithm begins by identifying a feasible path from \(s_{1}^{h}\) to \(g_{1}^{h}\), which is termed the predictive path. The algorithm then computes the flow capacity between each pair of nodes along this path, deriving the maximum flow value sustainable on it. This value serves as the predictive flow for the specified time slot, thereby defining the predictive flow for the e-TEG network. Details of the algorithm are presented in Algorithm 1. ```
0: Time-expanded graph \(\mathcal{F}_{h}=(\mathcal{V}_{h},\mathcal{A}_{h})\), source \(s_{1}^{h}\), and ground station \(g_{1}^{h}\)
1: Initialize predictive flow vertex set \(\bar{\mathcal{V}}\leftarrow\mathcal{V}_{h}\), edge set \(\bar{\mathcal{A}}\leftarrow\emptyset\), flow \(\hat{f}\leftarrow(\bar{\mathcal{V}},\bar{\mathcal{A}})\), and flow value \(\delta\leftarrow\infty\) [Initialize: preserve original nodes, reset edges, set bottleneck capacity to \(\infty\)]
2: Identify a path \(\mathcal{P}\) from \(s_{1}^{h}\) to \(g_{1}^{h}\) {BFS to find the first feasible path satisfying Equations (15)-(18)]
3:for each \((\mu,\
u)\in\mathcal{P}\)do
4: Add edge \((\mu,\
u)\) to \(\bar{\mathcal{A}}\) {Add edge to predictive flow network}
5: Update \(\delta\leftarrow\min(\delta,\mathcal{C}_{h}(\mu,\
u))\) [Track minimum capacity as bottleneck]
6:endfor
7:for each \((\mu,\
u)\in\mathcal{P}\)do
8: Set edge flow capacity \(\bar{c}(\mu,\
u)\leftarrow\delta\) [Set edge capacity to bottleneck value \(\delta\)]
9:endfor
10:return Predictive flow \(\hat{f}\) {Return flow network with nodes, edges, and allocated capacities }
```  
**Algorithm 1** Acquisition of predictive flow in the e-TEG network. Figure 5: A time-varying e-TEG satellite network model with one observation satellite, two relay satellites, and one ground station spanning time slots \(\tau_{1}\), \(\tau_{2}\), and an additional slot \(\tau_{3}\). As shown in Algorithm 1, the algorithm begins with initialization (Step 1), where the predictive flow \(\hat{f}\) is initialized with the graph's vertex set \(\mathcal{V}_{h}\), an empty edge set \(\bar{\mathcal{A}}\), and a flow value \(\delta\) set to infinity. In Step 2, the algorithm commences a traversal using the breadth-first search (BFS) method starting from \(s_{1}^{h}\), exploring all possible paths leading to \(\hat{g}_{1}^{h}\). For each candidate path identified during this traversal, it checks whether the path satisfies the constraints specified in Equations (15)-(18) in Section 3. Once the first feasible path is found during the search, it is selected as \(\mathcal{P}\).