Publikation:

Graphs with Distance Guarantees

Lade...
Vorschaubild

Dateien

377_1.pdf
377_1.pdfGröße: 1.62 MBDownloads: 351

Datum

1999

Autor:innen

Handke, Dagmar

Herausgeber:innen

Kontakt

ISSN der Zeitschrift

Electronic ISSN

ISBN

Bibliografische Daten

Verlag

Schriftenreihe

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
Dissertation
Publikationsstatus
Published

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)
510 Mathematik

Schlagwörter

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

Konferenz

Rezension
undefined / . - undefined, undefined

Forschungsvorhaben

Organisationseinheiten

Zeitschriftenheft

Zugehörige Datensätze in KOPS

Zitieren

ISO 690HANDKE, 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>

Interner Vermerk

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

Kontakt
URL der Originalveröffentl.

Prüfdatum der URL

Prüfungsdatum der Dissertation

December 10, 1999
Finanzierungsart

Kommentar zur Publikation

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