Research On Algorithms For Solving Two Minimum Spanning Tree Variant Problems

Many combinatorial optimization problems in the real world can be modeled as graph-based minimum spanning tree problems.Strong generalized minimum label spanning tree problem(SGMLST)and minimum spanning tree problem with conflicting edge pairs(MSTC)are two typical types of these problems,which have a wide range of applications in the design of communication and transportation networks,transmission system planning,and other fields.It is of practical significance and value to research these problems of NP-hard nature to save resources and optimize allocation.In recent years,researchers have proposed many approximate solutions;however,it is difficult for the current approximation algorithms to balance computational cost and search efficiency in the case of significant problem size.A community-based zigzag piloting algorithm for the SGMLST problem(CBZP)is proposed in this paper.At first,the CBZP algorithm derives the label graph based on the co-occurrence probability of the labels on the edge-labeled graph;Next,the label graph is divided into communities,and considering that the labels of the same community have a higher correlation,the community preferable index was designed as the basis for selecting community labels to construct the initial solution.For the chosen initial community labels,the addition or deletion of labels is piloted based on label additional index and label reduced index,so that the initial solution is optimized to obtain a better solution with fewer labels.The CBZP algorithm is experimentally proven to have higher accuracy and computing efficiency than existing methods on large-scale graph models.A heuristic algorithm based on key-edge and edge-priority is proposed for the MSTC problem(KE-EP).At first,the KE-EP algorithm performs a preprocessing operation on the original model to remove the false edges and the corresponding conflicting relations,and identify key-edges in the preprocessed MSTC model to construct the initial solution.Then the model is further simplified by removing the key edges and conflicting corresponding relations.An edge-priority function related to multiple parameters,such as the number of conflicting edges and weights,is defined to metricize the connected edges,edges are added sequentially to the initial set of solutions according to the edge-priority in the simplified model,and the key-edges need to be redetermined and the simplified model updated after each edge addition until the solution satisfies the conditions of the final solution.The KE-EP algorithm is experimentally proven to have better solution results.It has higher computing efficiency than existing methods on graph models with different sizes or a large number of conflicting edges.