USING GRAPH CENTRALITIES AND AN ITERATED LOCAL SEARCH ALGORITHM TO SOLVE THE GENERATOR TREE PROBLEM WITH MINIMUM NUMBER OF D-BRANCH VERTICES

    Given a connected, undirected, and unvalued graph G, the d-branch Minimum Vertex Spanning Tree (d-MBV) problem consists of finding a spanning tree that has the smallest number of vertices with degree strictly greater than d, for d ≥ 2. The direct application of this problem is, for example, in allocating switches in optical network projects. Graph centralities are measures that determine the importance of a vertex in a graph according to different criteria. This work shows that some centrality measures can identify vertices that should belong to a solution of the d-MBV problem. The use of these centralities was investigated in an ILS heuristic developed for the d-MBV problem to show how the use of different centralities influences the ability of the heuristic to find good-quality solutions.