Graphs with Distance Guarantees

Handke, Dagmar

Graphs with Distance Guarantees

Files

377_1.pdf(1.62 MB)

Date

1999

Authors

Handke, Dagmar

Publication type

Dissertation

Abstract

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.

Summary in another language

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.

Subject (DDC)

510 Mathematics

Keywords

Graphspanner,aufspannende Teilgraphen,graph theory,network design,graph spanner,spanning subgraph

Cite This

ISO 690

HANDKE, Dagmar, 1999. Graphs with Distance Guarantees [Dissertation]. Konstanz: University of Konstanz

BibTex

@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>

Examination date of dissertation

December 10, 1999