A New Nested Partitions Method for the Minimum labeling Spanning Tree Problem

In this study, a simulation-based optimization method called the Nested Partitions Method is used. Partitioning, Random sampling, Index Promising and back tracking is applied to reach a global Optimum. In this method local search is combined with global search to get more effectiveness. It reaches a global optimumwith probability one.Here this method is applied to find the Minimum labeling Spanning Tree. Given an undirected labeled connected graph, the minimum labeling spanning tree problem seeks a spanning tree whose edges have the smallest number of distinct labels. We present a numerical example to illustrate the method comprehensively.

Keywords:

Nested Partitions Method , The Minimum labeling Spanning Tree Problem , Simulation-basedoptimization