Research And Extension Of The Minimum Labeling Spanning Tree Problem

Many combinatorial optimization problems can be formulated on a graph where the possible solutions are spanning trees.There is a large and growing interest in both theoretical and practical aspects.For some of these problems there are polynomial-time algorithms,while most are NP-hard.The minimum labeling spanning tree(MLST) problem is an NP-hard problem in which,given a graph with labeled edges,one seeks a spanning tree with the least number of labels.Such a model can represent many real-world problems in telecommunications networks,power networks,and multimodal transportation networks.For example,in telecommunications networks,there are many different types of communications media.A communications node may communicate with different nodes by choosing different types of communications media.Given a set of communications network nodes,the problem is to find a spanning tree(a connected communications network) that uses as few communications types as possible.This spanning tree will reduce the construction cost and the complexity of the network.This paper researched on the minimal label spanning tree problem on the graph class of bounded tree width.In this graph class,we get an algorithm which is polynomial on the size of graph, showing that this problem is fixed-parameter tractable.Then heuristics for the minimum labeling spanning tree(MLST) problem were studied.Pilot method and a Variable Neighborhood Search(VNS) are proposed in this paper.They are compared with most classic algorithm recommended in the literature:MVCA.Nonparametric statistical tests show that the heuristics based on pilot method outperform the other algorithms tested,which in most cases present optimal value.Furthermore,a comparison with the results provided by an exact approach shows that we may quickly obtain optimal or near-optimal solutions with the proposed heuristics.At last, we research into the variant version of multi-labeled minimum labeling spanning tree problem,that is,each edge is labeled with more than one colors.We compare several heuristic methods and obtain satisfactory results.