# 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
In the network shown in Figure 5, a feasible path \(\mathcal{P}\), namely \(s_{1}^{3}\to\hat{s}_{1}^{3}\to\hat{r}_{2}^{3}\to r_{2}^{3}\to\hat{r}_{2}^{3} \to\hat{s}_{1}^{3}\), is identified from the source \(s_{1}^{3}\) to the ground station \(\hat{s}_{1}^{3}\). During Steps 3-6, each edge \((\mu,\
u)\), such as \((s_{1}^{3},\hat{s}_{1}^{3})\), \((\hat{s}_{1}^{3},\hat{r}_{2}^{3})\), \((\hat{r}_{2}^{3},r_{2}^{3})\), \((\hat{r}_{2}^{3},\hat{r}_{2}^{3})\), \((\hat{r}_{2}^{3},\hat{s}_{1}^{3})\) in the path \(\mathcal{P}\) is added to \(\bar{\mathcal{A}}\), and \(\delta\) is updated to reflect the minimum capacity \(\mathcal{C}_{h}(\mu,\
u)\), which in this case is 16, along the path. In Step 8, the capacity of each edge in \(\mathcal{P}\) is set to \(\delta\). Finally, in Step 10, the predictive flow \(\hat{f}\) is returned, comprising the updated vertex set, edge set, and capacities. _Feusibility analysis of predictive flow:_ The correctness and feasibility of the proposed algorithm are proven by demonstrating that the predicted flow \(\hat{f}\) satisfies the capacity constraints in Equation (15) and the flow conservation constraints in Equation (18). In Steps 3-6, Algorithm 1 calculates the minimum allowable flow \(\delta\) along the path \(\mathcal{P}\), defined as follows:  
\[\delta=\min\big{(}\mathcal{C}_{h}(\mu,\
u)\big{)},\forall(\mu,\
u)\in\mathcal{P} \tag{19}\]  
where \(\mathcal{C}_{h}(\mu,\
u)\) denotes the capacity of edge \((\mu,\
u)\). Since the flow on each edge \(\mathcal{F}_{h}(\mu,\
u)\) is limited by its capacity, that is,  
\[\mathcal{F}_{h}(\mu,\
u)\leq\mathcal{C}_{h}(\mu,\
u),\forall(\mu,\
u)\in \mathcal{P} \tag{20}\]  
it follows that the minimum flow \(\delta\) is also bounded by the edge capacities:  
\[\delta\leq\mathcal{C}_{h}(\mu,\
u),\forall(\mu,\
u)\in\mathcal{P} \tag{21}\]  
In Step 8 in Algorithm 1, the algorithm assigns this minimum flow \(\delta\) to each edge in the path \(\mathcal{P}\). As a result, in the final predictive flow \(\hat{f}\), the flow on each edge satisfies the capacity constraint:  
\[\mathcal{F}_{h}(\mu,\
u)\leq\mathcal{C}_{h}(\mu,\
u),\forall(\mu,\
u)\in \mathcal{P} \tag{22}\]  
Next, consider an arbitrary intermediate node \(v\) on the path \(\mathcal{P}\) (excluding the source node \(s_{1}^{h}\) and the ground station \(\hat{g}_{1}^{h}\)). Since the algorithm assigns a uniform flow value \(\delta\) to all edges in \(\mathcal{P}\), the inflow and outflow for any intermediate node \(v\) are equal:  
\[\sum_{\
u}f_{out}(v,\
u)=\sum_{\mu}f_{in}(\mu,v)=\delta,\forall v\in\mathcal{ V}\setminus\{s_{1}^{h},\hat{g}_{1}^{h}\} \tag{23}\]  
Thus, the predicted flow \(\hat{f}\) satisfies both the capacity and flow conservation constraints, ensuring the feasibility of the algorithm. _Complexity analysis:_ The time complexity of this algorithm depends on two primary components: identifying the feasible path \(\mathcal{P}\) and updating flow rates. The complexity of finding the path \(\mathcal{P}\) depends on the graph traversal method. The use of BFS to identify a path has a time complexity of \(O(V+E)\), where \(V\) and \(E\) denote the number of nodes and edges, respectively. Once the path \(\mathcal{P}\) is identified, the algorithm iterates through the edges in \(\mathcal{P}\) to calculate the minimum flow \(\delta\) and assign it to the edges. This step involves \(O(|\mathcal{P}|)\) iterations, where \(|\mathcal{P}|\) is the number of edges on the path. In the worst case, \(|\mathcal{P}|\) can equal \(O(V)\) if the path passes through all nodes of the graph. Combining these components, the overall time complexity of the algorithm is \(O(V+E+|\mathcal{P}|)\). In the worst-case scenario, where \(|\mathcal{P}|=O(V)\), the complexity simplifies to \(O(V+E)\). This indicates that the algorithm is efficient and scales linearly with the size of the graph, making it well-suited for dynamic e-TEG networks.