Publikation: Survivable Networks with Bounded Delay
Dateien
Datum
Autor:innen
Herausgeber:innen
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
URI (zitierfähiger Link)
Internationale Patentnummer
Link zur Lizenz
Angaben zur Forschungsförderung
Projekt
Open Access-Veröffentlichung
Core Facility der Universität Konstanz
Titel in einer weiteren Sprache
Publikationstyp
Publikationsstatus
Erschienen in
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.
Zusammenfassung in einer weiteren Sprache
Fachgebiet (DDC)
Schlagwörter
Konferenz
Rezension
Zitieren
ISO 690
CICERONE, Serafino, Gabriele DI STEFANO, Dagmar HANDKE, 1998. Survivable Networks with Bounded DelayBibTex
@unpublished{Cicerone1998Survi-6088, year={1998}, title={Survivable Networks with Bounded Delay}, author={Cicerone, Serafino and Di Stefano, Gabriele and Handke, Dagmar} }
RDF
<rdf:RDF xmlns:dcterms="http://purl.org/dc/terms/" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" xmlns:bibo="http://purl.org/ontology/bibo/" xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#" xmlns:foaf="http://xmlns.com/foaf/0.1/" xmlns:void="http://rdfs.org/ns/void#" xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > <rdf:Description rdf:about="https://kops.uni-konstanz.de/server/rdf/resource/123456789/6088"> <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/> <dcterms:issued>1998</dcterms:issued> <dc:contributor>Cicerone, Serafino</dc:contributor> <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/> <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/6088"/> <dcterms:title>Survivable Networks with Bounded Delay</dcterms:title> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T16:09:28Z</dcterms:available> <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/6088/1/preprint_081.pdf"/> <dcterms:abstract xml:lang="eng">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.<br /><br />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.<br /><br />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.</dcterms:abstract> <foaf:homepage rdf:resource="http://localhost:8080/"/> <dc:language>eng</dc:language> <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/> <dc:contributor>Di Stefano, Gabriele</dc:contributor> <dc:creator>Di Stefano, Gabriele</dc:creator> <dc:creator>Handke, Dagmar</dc:creator> <dc:format>application/pdf</dc:format> <dc:rights>terms-of-use</dc:rights> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T16:09:28Z</dc:date> <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/6088/1/preprint_081.pdf"/> <dc:contributor>Handke, Dagmar</dc:contributor> <dc:creator>Cicerone, Serafino</dc:creator> </rdf:Description> </rdf:RDF>