Given a connected graph G a vertex is said to be of the branch type if its degree is greater than 2. We consider the problem of nding a spanning tree of G which minimizes the number of branch vertices. Such a problem has been proved to be NP-complete, and some efcient heuristics to solve it have been proposed in the literature. In the paper we present a new heuristic algorithm based on solving the Lagrangean dual of the original mixed integer programming problem by means of a dual ascent procedure requiring update of one multiplier at a time.
File in questo prodotto:
Non ci sono file associati a questo prodotto.