CINECA IRIS Institutional Research Information System
IRIS è la piattaforma adottata dall’Università degli Studi di Udine per gestire l’archivio aperto dei prodotti della ricerca. L’archivio contiene articoli, contributi in volume, monografie, interventi pubblicati in atti di convegno, Tesi di dottorato e altri materiali.
EnglishThis chapter is devoted to compact extended formulations of tree problems. First, we give a compact extended formulation for the relaxation of the Steiner tree problem. We then describe the well-known minimum spanning tree problem, for which there exist polynomial algorithms and exponential-size models. We use both LP techniques and nonnegative rank factorization to provide compact extended formulations. Finally we present two NP-hard problems related to spanning trees of some relevance in the literature. The first one deals with bounded-degree spanning trees and the second one with minimal routing-cost trees, that have a considerable importance in network design and computational biology.
| Titolo: | Trees | |
| Autori: | ||
| Data di pubblicazione: | 2018 | |
| Serie: | ||
| Abstract: | This chapter is devoted to compact extended formulations of tree problems. First, we give a compact extended formulation for the relaxation of the Steiner tree problem. We then describe the well-known minimum spanning tree problem, for which there exist polynomial algorithms and exponential-size models. We use both LP techniques and nonnegative rank factorization to provide compact extended formulations. Finally we present two NP-hard problems related to spanning trees of some relevance in the literature. The first one deals with bounded-degree spanning trees and the second one with minimal routing-cost trees, that have a considerable importance in network design and computational biology. | |
| Handle: | http://hdl.handle.net/11390/1214317 | |
| ISBN: | 978-3-319-63975-8 978-3-319-63976-5 | |
| Appare nelle tipologie: | 2.1 Contributo in volume (Capitolo o Saggio) |
File in questo prodotto:
Copyright © 2022