Finding The P-Topk Minimum Spanning Trees In An Uncertain Graph

The minimum spanning tree(MST)plays an important role in network designing,VLSI and traffic construction,etc.However,it becomes non-applicable when the uncertainty exists in these applications.For example,the link between two nodes is usually unstable in the wireless sensor network and the road is not always clear due to the traffic congestion,MST in such an uncertain graph is also uncertain.Therefore,the research of MST problem on an uncertain graph is very important.This thsis studied the MST querying problem on the edge-uncertain graph.To be concretely,the weight of each edge is a tuple consisting of the cost weight and the existing probability of the edge,the cost weight is meaningful only when the edge exists.The purpose of this paper is to find the P-TopK minimum spanning trees in such an uncertain graph.Firstly,an improved algorithm based on the dynamical combination algorithm(CA_Dyn)was proposed,called the combination filtering algorithm based on multidimensional groups(CA_MG).It proposed a new grouping method for all combinations in an uncertain graph.This method helps improve the filtering capacity greatly.In addition,an optimization strategy based on the cycles was proposed to help accelerate the querying procedure.The experiments showed that CA_MG has the best performance among all the algorithms based on the combination,the optimization strategy based on the cycles also helps to improve the efficiency of CA_MG.In fact,the number of combinations is very large,which leads to the inefficiency of the algorithms based on combinations.Although CA_Dyn and CA_MG filter some of the combinations by dividing them into groups,the filtering capacity is still limited.Based on these,we put forward the filtering algorithm based on K maximum upper bound trees(FA_KMUBT).Firstly,the concepts of maximum upper bound tree(MUBT)and the K maximum upper bound trees(KMUBT)were introduced,and then the method to generate KMUBT was presented,the P-TopK MST querying procedure is carried out when the upper bound trees are generated in descending order.The experimental results showed that FA_KMUBT has the best performance among all the existing algorithms due to its smaller candidate space.Considering the large scale of calculation of this problem,a basic parallel computing scheme based on CA_MG was proposed.In this scheme,we firstly introduced the concept of combination partitioning and then the combination partitioning algorithm was presented to divide all the combinations into different parts.By delivering different parts to different processors and all the processors computing in the same time,we can finally obtain the P-TopK MST result.The experimental results indicated the parallel version of CA_MG performs better and better with the increasing of the num of processors.