KOPS - Das Institutionelle Repositorium der Universität Konstanz
# Survivable Networks with Bounded Delay

- Startseite
- →
- Informatik und Informationswissenschaft
- →
- Informatik und Informationswissenschaft
- →
- Dokumentanzeige

Publikationstyp: | Preprint |

URI (zitierfähiger Link): | http://nbn-resolving.de/urn:nbn:de:bsz:352-opus-20574 |

Autor/innen: | Cicerone, Serafino; Di Stefano, Gabriele; Handke, Dagmar |

Erscheinungsjahr: | 1998 |

Schriftenreihe: | Konstanzer Schriften in Mathematik und Informatik ; 81 |

Zusammenfassung: |
We investigate new classes of graphs which 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 a first part, we consider k-self-spanners, the class of graphs where the distance constraint holds even for an unlimited number of edge faults. In particular, we give (non-algorithmic) strict characterizations of the graph classes and show that the problem of minimizing k such that a given graph is a k-self-spanner is co-NP-complete. For small values of k, characterizations in terms of possible topologies of biconnected components are given. In the second case, 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 graph operations such as Cartesian product and split composition affect the self-spanner properties of the composed graph. We also investigate several popular network topologies with respect to their self-spanner properties. |

Fachgebiet (DDC): | 004 Informatik |

Link zur Lizenz: | Nutzungsbedingungen |

Prüfsumme:
MD5:ab994661cdea995c0ecc90f1e02dba3c

CICERONE, Serafino, Gabriele DI STEFANO, Dagmar HANDKE, 1998. Survivable Networks with Bounded Delay

@unpublished{Cicerone1998Survi-6088, title={Survivable Networks with Bounded Delay}, year={1998}, author={Cicerone, Serafino and Di Stefano, Gabriele and Handke, Dagmar} }

preprint_081.pdf | 113 |