# An Accelerated Maximum Flow Algorithm with Prediction Enhancement in Dynamic LEO Networks
## 4 Predictive Acceleration Algorithm for e-TEG Satellite Networks
### Predictive Accelerated e-TEG Network Maximum Flow Algorithm
Complexity analysisThe time complexity of the predictive accelerated maximum flow algorithm depends on the relationship between the predictive flow \(\hat{f}\) and the optimal flow \(f^{*}_{c}\) on the graph \(G\). Using the predictive flow \(\hat{f}\) as the initial seed significantly reduces the number of iterations required to compute the maximum flow compared to starting from zero. The Ford-Fulkerson algorithm operates iteratively, augmenting the flow value until it reaches the maximum flow. Each iteration of the algorithm finds an augmenting path and sends flow along it, requiring \(O(E)\) time, where \(E\) is the number of edges in the graph. The number of iterations is proportional to the difference in flow values between the predictive flow and the optimal flow, specifically at most \(val(f_{c}^{*})-val(\hat{f})\) iterations. In Steps 2-4, the algorithm adjusts the residual capacities of edges based on the predictive flow \(\hat{f}\). This operation requires \(O(E_{f})\) time, where \(E_{f}\) is the number of edges in the predictive flow. In Step 5, the Ford-Fulkerson algorithm computes the residual flow \(f_{\text{res}}\) by iterating over augmenting paths. For each augmenting path, the runtime is \(O(E)\), and the number of iterations is bounded by \(val(f_{c}^{*})-val(\hat{f})\). Hence, the runtime of this step is as follows:  
\[O(E\cdot(val(f_{c}^{*})-val(\hat{f}))) \tag{24}\]  
In Steps 6-8, the algorithm updates the final residual capacities by subtracting the flows of \(\hat{f}\) and \(f_{\text{res}}\). This step requires \(O(E)\) time. Combining these components, the total runtime is dominated by the Ford-Fulkerson computation and can be expressed as follows:  
\[O(E\cdot(val(f_{c}^{*})-val(\hat{f}))+E) \tag{25}\]  
which simplifies to \(O(E\cdot(val(f_{c}^{*})-val(\hat{f})))\) in practical scenarios where \(val(f_{c}^{*})-val(\hat{f})\gg 1\). Let \(\eta=||\hat{f}-f_{c}^{*}||_{1}\) represent the prediction error, which quantifies the difference between the predictive flow \(\hat{f}\) and the optimal flow \(f_{c}^{*}\). This error provides an upper bound on the number of iterations required by the algorithm, as \(val(f_{c}^{*})-val(\hat{f})\leq\eta\). Therefore, the runtime can be further bounded by the following:  
\[O(E\cdot\eta) \tag{26}\]  
where \(\eta\) reflects both the quality of the predictive flow and the efficiency of the algorithm. The quality of the predictive flow \(\hat{f}\) is measured as follows:  
\[\eta(\hat{f})=\min_{f^{*}\in F^{*}}||\hat{f}-f^{*}||_{1} \tag{27}\]  
where \(F^{*}\) represents the set of all possible maximum flows. In cases where there are multiple maximum flow solutions, \(\eta(\hat{f})\) is calculated with respect to the closest solution in \(F^{*}\). The smaller the prediction error \(\eta(\hat{f})\), the fewer iterations are required to reach the optimal flow, and thus, the faster the algorithm converges. The runtime of the algorithm depends linearly on the size of the graph (that is, \(E\)) and the prediction error \(\eta\). By leveraging the predictive flow \(\hat{f}\), the algorithm significantly reduces the number of iterations required to compute the maximum flow. This makes the algorithm particularly efficient for dynamic e-TEG networks, where predictive flows can be updated frequently to match the evolving topology.