Graphs with Distance Guarantees

Cite This

Files in this item

Checksum: MD5:80c39821d16710f8c55b55c69f8efcb5

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

@phdthesis{Handke1999Graph-628, title={Graphs with Distance Guarantees}, year={1999}, author={Handke, Dagmar}, address={Konstanz}, school={Universität Konstanz} }

<rdf:RDF xmlns:dcterms="" xmlns:dc="" xmlns:rdf="" xmlns:bibo="" xmlns:dspace="" xmlns:foaf="" xmlns:void="" xmlns:xsd="" > <rdf:Description rdf:about=""> <dcterms:issued>1999</dcterms:issued> <dspace:hasBitstream rdf:resource=""/> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dc:format>application/pdf</dc:format> <dc:creator>Handke, Dagmar</dc:creator> <dcterms:hasPart rdf:resource=""/> <dc:rights>terms-of-use</dc:rights> <dcterms:available rdf:datatype="">2011-03-22T17:45:17Z</dcterms:available> <bibo:uri rdf:resource=""/> <dcterms:rights rdf:resource=""/> <dc:language>eng</dc:language> <dc:date rdf:datatype="">2011-03-22T17:45:17Z</dc:date> <foaf:homepage rdf:resource="http://localhost:8080/jspui"/> <dcterms:isPartOf rdf:resource=""/> <dspace:isPartOfCollection rdf:resource=""/> <dcterms:title>Graphs with Distance Guarantees</dcterms:title> <dc:contributor>Handke, Dagmar</dc:contributor> <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> </rdf:Description> </rdf:RDF>

Downloads since Oct 1, 2014 (Information about access statistics)

377_1.pdf 313

This item appears in the following Collection(s)

Search KOPS


My Account