Study Of The Rapid Algorithms For Vital Edge On Dynamic Network

Many methods for solving vital edge in specific application have been presented, due to its significant value in utilization and research. In order to evaluate the important degrees of edges in uncertain flow network, this paper proposes a model based on maximum flow and flow reliability. The important degree of edge can be estimated according to the change of maximum flow and capacity reliability when the edge is valid and invalid. However, the process of calculating maximum flow is complex, and the calculation of capacity reliability is NP-hard. Thus, in huge network, the method of recalculating them with traditional algorithms cannot satisfy the requirement of real-time. Therefore, the research focus of this paper is how to rapidly calculate maximum flow and capacity reliability in dynamic network.In the algorithm of maximum flow, the process to search next augmenting path is critical and time-consume. Thus, this paper proposes an incremental algorithm for solving maximum flow (MFIA_PC), on the basis of the cache of simple paths, which could be traversed when edge is invalid to accelerate the research speed of next augmenting path. However, the efficiency of this algorithm is inversely with the number of simple paths, therefore this paper proposes an algorithm of maximum flow based on augmented routing tree (MFIA_ART) to avoid traversing invalid path with saturated edge. This is more effective than MFIA_PC.Most of algorithms for capacity reliability contain a large of repeat calculation of maximum flow, thus this paper proposes an algorithm of capacity reliability based on d-flow lowers (DFP_AT). In this method, one d-flow lower X is got firstly, then all d-flow lowers of network are produced with transmission of flow based on X. Finally, capacity reliability is computed through creating an accept tree. In order to satisfy real-time requirement, this paper proposes an incremental algorithm based DFP_AT. It uses data cache and other method to promote the calculation efficiency of capacity reliability.In the end, we test the accuracy of all algorithms proposed in this paper with series experiments. The performances of incremental algorithms are examined through comparison with correspondedclassic algorithms. Moreover, the advantages and weakness of the estimation model present in this paper are analyzed through comparison with other model.