Publikation:

Survivable Networks with Bounded Delay

Lade...
Vorschaubild

Dateien

preprint_081.pdf
preprint_081.pdfGröße: 333.16 KBDownloads: 202

Datum

1998

Autor:innen

Cicerone, Serafino
Di Stefano, Gabriele
Handke, Dagmar

Herausgeber:innen

Kontakt

ISSN der Zeitschrift

Electronic ISSN

ISBN

Bibliografische Daten

Verlag

Auflagebezeichnung

DOI (zitierfähiger Link)
ArXiv-ID

Internationale Patentnummer

Angaben zur Forschungsförderung

Projekt

Open Access-Veröffentlichung
Open Access Green
Core Facility der Universität Konstanz

Gesperrt bis

Titel in einer weiteren Sprache

Publikationstyp
Preprint
Publikationsstatus
Published

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)
004 Informatik

Schlagwörter

Konferenz

Rezension
undefined / . - undefined, undefined

Forschungsvorhaben

Organisationseinheiten

Zeitschriftenheft

Zugehörige Datensätze in KOPS

Zitieren

ISO 690CICERONE, Serafino, Gabriele DI STEFANO, Dagmar HANDKE, 1998. Survivable Networks with Bounded Delay
BibTex
@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.&lt;br /&gt;&lt;br /&gt;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.&lt;br /&gt;&lt;br /&gt;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&gt;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>

Interner Vermerk

xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter

Kontakt
URL der Originalveröffentl.

Prüfdatum der URL

Prüfungsdatum der Dissertation

Finanzierungsart

Kommentar zur Publikation

Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Begutachtet
Diese Publikation teilen