Graphs with Distance Guarantees
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
Sammlungen
Core Facility der Universität Konstanz
Titel in einer weiteren Sprache
Publikationstyp
Publikationsstatus
Erschienen in
Zusammenfassung
One goal in network design is the construction of sparse networks that guarantee short distances with respect to some given distance requirements. By this, it can be guaranteed, for example, that delays that are incurred by link faults are bounded. An appropriate graph-theoretic model for this is the concept of k-spanners: Given a graph G, a k-spanner of G is a spanning subgraph S, such that the distance between any two vertices in S is at most k times longer than the distance in G. Research in this area has mainly concentrated on two aspects: minimum k-spanners, i.e., k-spanners that contain the fewest edges among all k-spanners, and tree k-spanners, i.e., spanners that are trees. In this thesis, we use k-spanners to model further desirable properties from network design (such as reliability) within a graph-theoretic framework. Our main emphasis is on sparse graphs that guarantee short distances, and we are interested in simple structures and fault-tolerance.
Zusammenfassung in einer weiteren Sprache
Ein wichtiges Teilproblem beim Entwurf von Netzwerken ist das Finden von dünnen Netzwerken, in denen die Abstände zwischen je zwei Knoten nicht zu groß bzgl. vorgegebener Entfernungsbedingungen werden. Auf diese Weise kann beispielsweise garantiert werden, dass Verzögerungen durch den Wegfall von Verbindungen unter Kontrolle gehalten werden. Ein geeignetes graphentheroretisches Modell dafür sind k-Spanner: Ein aufspannender Teilgraph S heißt k-Spanner eines Graphen G für ein k>= 1, falls die Distanz in S für jedes Knotenpaar höchstens das k-fache der Distanz in G ist. Die Forschung im bereich der k-Spanner hat sich meist auf das Studium von minimalen k-Spannern (also k-Spannern mit der kleinstmöglichen Kantenzahl) oder k-Baumspannern (also k-Spannern, die Baumsptruktur haben) konzentriert. In dieser Dissertation verwenden wir das Konzept der k-Spanner, um zusätzliche wünschenswerte Eigenschaften (wie zum Beispiel Zuverlässigkeit) graphentheoretisch zu fassen. Wir beschäftigen uns dabei hauptsächlich mit dünnen Graphen, die kurze Distanzen garantieren und dabei eine möglichst einfache Struktur besitzen beziehungsweise fehlertolerant sind.
Fachgebiet (DDC)
Schlagwörter
Konferenz
Rezension
Zitieren
ISO 690
HANDKE, Dagmar, 1999. Graphs with Distance Guarantees [Dissertation]. Konstanz: University of KonstanzBibTex
@phdthesis{Handke1999Graph-628,
year={1999},
title={Graphs with Distance Guarantees},
author={Handke, Dagmar},
address={Konstanz},
school={Universität Konstanz}
}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/628">
<foaf:homepage rdf:resource="http://localhost:8080/"/>
<dc:creator>Handke, Dagmar</dc:creator>
<dcterms:abstract xml:lang="eng">One goal in network design is the construction of sparse networks that guarantee short distances with respect to some given distance requirements. By this, it can be guaranteed, for example, that delays that are incurred by link faults are bounded. An appropriate graph-theoretic model for this is the concept of k-spanners: Given a graph G, a k-spanner of G is a spanning subgraph S, such that the distance between any two vertices in S is at most k times longer than the distance in G. Research in this area has mainly concentrated on two aspects: minimum k-spanners, i.e., k-spanners that contain the fewest edges among all k-spanners, and tree k-spanners, i.e., spanners that are trees. In this thesis, we use k-spanners to model further desirable properties from network design (such as reliability) within a graph-theoretic framework. Our main emphasis is on sparse graphs that guarantee short distances, and we are interested in simple structures and fault-tolerance.</dcterms:abstract>
<dc:contributor>Handke, Dagmar</dc:contributor>
<dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-22T17:45:17Z</dcterms:available>
<dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-22T17:45:17Z</dc:date>
<bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/628"/>
<dcterms:title>Graphs with Distance Guarantees</dcterms:title>
<dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/628/1/377_1.pdf"/>
<dc:format>application/pdf</dc:format>
<void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
<dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/39"/>
<dcterms:issued>1999</dcterms:issued>
<dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/39"/>
<dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/>
<dc:rights>terms-of-use</dc:rights>
<dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/628/1/377_1.pdf"/>
<dc:language>eng</dc:language>
</rdf:Description>
</rdf:RDF>
