# An Accelerated Maximum Flow Algorithm with Prediction Enhancement in Dynamic LEO Networks
## 3 System Model and Problem Formulation
### Construction of the e-TEG Satellite Network  
To address data flow optimization in dynamic, resource-constrained LEO satellite networks, we construct the e-TEG framework. It captures network topology and resource constraints across discrete time slots, enabling time-aware maximum flow computation. The e-TEG maps satellites, ground stations, and their communication links into an expanded graph that reflects temporal and resource-dependent relationships. The node set \(\mathcal{V}^{*}\) and the arc set \(\mathcal{A}^{*}\) of the e-TEG are derived as follows. First, for each satellite and the ground station, a distinct node is created for every time slot \(\tau_{h}\), where \(1\leq h\leq k\). For a satellite \(v_{i}\), this results in a series of temporal replicas \(\{v_{i}^{1},v_{i}^{2},\ldots,v_{i}^{k}\}\), each corresponding to its state in a specific time slot. Similarly, the source satellite \(s_{1}\) and the ground station \(g_{1}\) are represented as \(\{s_{1}^{1},s_{1}^{2},\ldots,s_{1}^{k}\}\) and \(\{g_{1}^{1},g_{1}^{2},\ldots,g_{1}^{k}\}\), respectively. Virtual nodes \(\mathcal{V}_{t}\) and \(\mathcal{V}_{a}\) are introduced to model the sending and receiving states of data flow at each time slot, completing the construction of the node set:  
\[\mathcal{V}^{*}=\mathcal{V}_{s}\cup\mathcal{V}_{r}\cup\mathcal{V}_{g}\cup \mathcal{V}_{t}\cup\mathcal{V}_{a} \tag{9}\]  
where \(\mathcal{V}_{s}\), \(\mathcal{V}_{r}\), and \(\mathcal{V}_{g}\) correspond to the source, relay, and ground station nodes across time slots, respectively. Next, arcs are added to model the data flow and its constraints. For each node \(v_{i}^{h}\), an arc \((v_{i}^{h},v_{i}^{h+1})\) is created to represent data caching across consecutive time slots. These arcs form the caching set \(\mathcal{A}_{c}\). Additionally, virtual arcs \((v_{i}^{h},\hat{v}_{i}^{h})\) and \((\hat{v}_{i}^{h},v_{i}^{h})\) are added to connect physical nodes with their virtual sending and receiving counterparts. These virtual arcs, collectively denoted by \(\mathcal{A}_{s}\) and \(\mathcal{A}_{r}\), enable the modeling of data flow within a single time slot. Finally, transmission arcs \((\hat{v}_{i}^{h},\hat{v}_{j}^{h})\) are introduced to represent feasible data transfer between nodes \(v_{i}^{h}\) and \(v_{j}^{h}\) within a time slot \(\tau_{h}\). These arcs, denoted as \(\mathcal{A}_{e}\), are only added if a direct communication link exists between \(v_{i}\) and \(v_{j}\) during \(\tau_{h}\), subject to LoS constraints. The complete arc set is, therefore, expressed as follows:  
\[\mathcal{A}^{*}=\mathcal{A}_{c}\cup\mathcal{A}_{s}\cup\mathcal{A}_{r}\cup \mathcal{A}_{e} \tag{10}\]  
Each arc in \(\mathcal{A}^{*}\) is assigned a capacity to reflect the network's constraints. For transmission arcs \((\hat{v}_{i}^{h},\hat{v}_{j}^{h})\in\mathcal{A}_{e}\), the capacity \(\mathcal{C}^{*}_{\hat{v}_{i}^{h},\hat{v}_{j}^{h}}\) is calculated as follows:  
\[\mathcal{C}^{*}_{\hat{v}_{i}^{h},\hat{v}_{j}^{h}}=\int_{\tau_{h}}R_{v_{i}^{h},v _{j}^{h}}(t)\,dt \tag{11}\]  
where \(R_{v_{i}^{h},v_{j}^{h}}(t)\) is the data transmission rate between \(v_{i}\) and \(v_{j}\) during \(\tau_{h}\). For caching arcs \((v_{i}^{h},v_{i}^{h+1})\in\mathcal{A}_{c}\), the capacity is set to the buffer size \(S_{v_{i}}\). Virtual arcs \(\mathcal{A}_{s}\) and \(\mathcal{A}_{r}\) are assigned infinite capacity to ensure they do not impose additional constraints. In the e-TEG model, each satellite \(v_{i}^{h}\) is associated with a processing capacity \(C_{i}^{h}\) at the end of each time slot \(\tau_{h}\). This value represents the maximum amount of data the satellite can process during that time, taking into account its available energy and hardware limitations.