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

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.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11386/4168853
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact