Study Of The D-Flow Problem On Uncertain Graph

The uncertain graph is a hot topic in current research. The most reliable maximum flow problem (MRMF) on uncertain graphs is proposed to find the most reliable distribution to transmit maximum flow. It is an important problem to choose optimal transmission paths and build reliable networks, etc. However, MRMF is mainly based on two-state uncertain graph and the actual network is like as multi-state graph. In addition, the demand flow d usually less then the maximum flow. So this paper proposes the most reliable d flow problem (d-MRF) through multi-state graphs. It studies efficient solutions to find the most reliable distribution to transmit d flow from source node to sink node.Firstly, based on the possible world model, this thesis defines the uncertain graph and introduces reliability calculation model of d-MRF. Then, a space decomposition algorithm based on d flow (SDBA-d) is proposed. It divides subgraph space into several disjointed and closed intervals, find all intervals which can transmit d flow, and then get the largest lower bound which is the most reliable d flow distribution.Furthermore, a shortest path combination approximation algorithm (SPCAA) is put forward. Find shortest path, accumulate bottleneck capacity until satisfy demand flow, so can obtain a more reliable d flow distribution. However, as the oscillation of algorithm accuracy, SPCAA is not worked as an separate method, but as a preprocessor to get an improved space decomposition algorithm (ISDA-d). Get a d flow distribution from SPCAA algorithm, use it to divide subgraph space and as athreshold to filter out a large number of low probability intervals. In order to enhance the oscillation of SPCAA algorithm, this paper raise a path sampling approximate algorithm. For each iteration, choose N shortest path to combine paths and get sets of d flow distribution, then the largest one as the optimal distribution of current simple N. With the increase of N, the d flow distribution would convergence. then get the most reliable approximate d flow distribution. Experimental results show the effectiveness and efficiency of ISDA-d over SDBA-d. PSAA algorithm can get a more reliable d flow distribution and can be applied to spares graph, small demand flow, etc.