A prediction-based heuristic for the Minimum Branch Vertices Spanning Tree Problem
Massinissa Merabet  1@  
1 : SAMOVAR
École Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)

The MBVST problem is motivated by the design of optical networks. The optical Broadcast communication in based on spanning trees. If the degree of an optical node is strictly greater than two, then the light signal must be split by a sophisticated switch. As the number of used switches implies an increment of the optical network cost, a minimization of this number is often required. Considering a connected graph representing the optical network, the MBVST problem aims to find a spanning tree of G with a minimum number of branch vertices. This problem is known to be NP-hard, therefore different heuristic algorithms were proposed in the literature. In this paper, we introduce an heuristic algorithm based on the edge prediction to obtain an approximated solution which is sightly better then the best known method.


Personnes connectées : 2 Vie privée
Chargement...