Abordagem de refinamento iterativo para o problema da árvore geradora com número mínimo de vértices Branch

Abstract

Given a connected, undirected, unweighted graph G=(V,E) the Minimum Branch Vertices Problem (MBV) consists in finding a spanning tree T of G that contains the minimum number of vertices with degree greater than or equal to 3, also called branch vertices. This problem arises in the design of optical multicast networks when it is necessary to decide where to allocate a special kind of WDM switch, called light-splitting switches. This problem is proved to be NP-Complete. In this work the MBV problem has been investigated with a new heuristic based on the Iterative Refinement Approach (IR), where an unconstrained spanning tree is changed using a edge-replacement strategy until the tree topology achieves a minimum number of branch vertices. Experiments were done applying the IR algorithm over six sets of instances, and the results were compared with two other heuristics for the MBV problem. The analysis of the results suggest that the IR algorithm can find better solutions than these heuristics as the graph density increases.