CINECA IRIS Institutional Research Information System
IRIS è la soluzione IT che facilita la raccolta e la gestione dei dati relativi alle attività e ai prodotti della ricerca. Fornisce a ricercatori, amministratori e valutatori gli strumenti per monitorare i risultati della ricerca, aumentarne la visibilità e allocare in modo efficace le risorse disponibili.
EnglishWe introduce new classes of graphs to investigate networks that guarantee constant delays even in the case of multiple edge failures. This means the following: as long as two vertices remain connected if some edges have failed, then the distance between these vertices in the faulty graph is at most a constant factor k times the original distance. In this extended abstract, we consider the case where the number of edge failures is bounded by a constant l. These graphs are called (k, l)–self-spanners. We prove that the problem of maximizing l for a given graph when k > 4 is fixed is NP-complete, whereas the dual problem of minimizing k when l is fixed is solvable in polynomial time. We show how the Cartesian product affects the self-spanner properties of the composed graph. As a consequence, several popular network topologies (like grids, tori, hypercubes, butterflies, and cube-connected cycles) are investigated with respect to their self-spanner properties.
| Titolo: | Survivable Networks with Bounded Delay: The Edge Failure Case | |
| Autori: | ||
| Data di pubblicazione: | 1999 | |
| Rivista: | ||
| Abstract: | We introduce new classes of graphs to investigate networks that guarantee constant delays even in the case of multiple edge failures. This means the following: as long as two vertices remain connected if some edges have failed, then the distance between these vertices in the faulty graph is at most a constant factor k times the original distance. In this extended abstract, we consider the case where the number of edge failures is bounded by a constant l. These graphs are called (k, l)–self-spanners. We prove that the problem of maximizing l for a given graph when k > 4 is fixed is NP-complete, whereas the dual problem of minimizing k when l is fixed is solvable in polynomial time. We show how the Cartesian product affects the self-spanner properties of the composed graph. As a consequence, several popular network topologies (like grids, tori, hypercubes, butterflies, and cube-connected cycles) are investigated with respect to their self-spanner properties. | |
| Handle: | http://hdl.handle.net/11697/42122 | |
| ISBN: | 3-540-66916-7 | |
| Appare nelle tipologie: | 4.1 Contributo in Atti di convegno |
File in questo prodotto:
http://hdl.handle.net/11697/42122
Copyright © 2021