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.
A Dual Ascent Approach to the Bounded-Degree Spanning Tree Problem
GENTILI, Monica;CERULLI, Raffaele;
2007-01-01
Abstract
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.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
