http://www.cnr.it/ontology/cnr/individuo/prodotto/ID7198
Edge-connectivity augmentation and network matrices (Articolo in rivista)
- Type
- Label
- Edge-connectivity augmentation and network matrices (Articolo in rivista) (literal)
- Anno
- 2004-01-01T00:00:00+01:00 (literal)
- Alternative label
Conforti, M.; Galluccio, A.; Proietti, G. (2004)
Edge-connectivity augmentation and network matrices
in Lecture notes in computer science
(literal)
- Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#autori
- Conforti, M.; Galluccio, A.; Proietti, G. (literal)
- Pagina inizio
- Pagina fine
- Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#numeroVolume
- Rivista
- Note
- ISI Web of Science (WOS) (literal)
- Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#affiliazioni
- Univ Padova, Dipartimento Matemat, I-35131 Padua, Italy
CNR, Ist Anal Sistemi & Informat, I-00185 Rome, Italy
Univ Aquila, Dipartimento Informat, I-67010 Coppito, Italy (literal)
- Titolo
- Edge-connectivity augmentation and network matrices (literal)
- Abstract
- We study the following NP-hard graph augmentation problem: Given
a weighted graph G and a connected spanning subgraph H of G,
find a minimum weight set of edges of G to be added to H so
that H becomes 2-edge-connected. We provide a formulation of
the problem as a set covering problem, and we analyze the
conditions for which the linear programming relaxation of our
formulation always gives an integer solution. This yields
instances of the problem that can be solved in polynomial time. As
we will show in the paper, these particular instances have not
only theoretical but also practical interest, since they model a
wide range of survivability problems in communication networks. (literal)
- Prodotto di
- Autore CNR
Incoming links:
- Prodotto
- Autore CNR di
- Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#rivistaDi
