KOPS - The Institutional Repository of the University of Konstanz

Geometric Speed-Up Techniques for Finding Shortest Paths in Large Sparse Graphs

Geometric Speed-Up Techniques for Finding Shortest Paths in Large Sparse Graphs

Cite This

Files in this item

Checksum: MD5:50b3be6c00c83e2e707f92fa8e6b69dc

WAGNER, Dorothea, Thomas WILLHALM, 2003. Geometric Speed-Up Techniques for Finding Shortest Paths in Large Sparse Graphs

@unpublished{Wagner2003Geome-6328, title={Geometric Speed-Up Techniques for Finding Shortest Paths in Large Sparse Graphs}, year={2003}, author={Wagner, Dorothea and Willhalm, Thomas} }

<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/rdf/resource/123456789/6328"> <dc:creator>Willhalm, Thomas</dc:creator> <dcterms:title>Geometric Speed-Up Techniques for Finding Shortest Paths in Large Sparse Graphs</dcterms:title> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T16:11:29Z</dcterms:available> <dcterms:abstract xml:lang="eng">In this paper, we consider Dijkstra's algorithm for the single source single target shortest paths problem in large sparse graphs. The goal is to reduce the response time for online queries by using precomputed information. For the result of the preprocessing, we admit at most linear space. We assume that a layout of the graph is given. From this layout, in the preprocessing, we determine for each edge a geometric object containing all nodes that can be reached on a shortest path starting with that edge. Based on these geometric objects, the search space for online computation can be reduced significantly. We present an extensive experimental study comparing the impact of different types of objects. The test data we use are traffic networks, the typical field of application for this scenario.</dcterms:abstract> <dc:rights>terms-of-use</dc:rights> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T16:11:29Z</dc:date> <dc:contributor>Willhalm, Thomas</dc:contributor> <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/rdf/resource/123456789/36"/> <dc:contributor>Wagner, Dorothea</dc:contributor> <foaf:homepage rdf:resource="http://localhost:8080/jspui"/> <dc:language>eng</dc:language> <dc:creator>Wagner, Dorothea</dc:creator> <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/6328/1/preprint_183.pdf"/> <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/6328/1/preprint_183.pdf"/> <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/> <dcterms:issued>2003</dcterms:issued> <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/rdf/resource/123456789/36"/> <dc:format>application/pdf</dc:format> <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/6328"/> </rdf:Description> </rdf:RDF>

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

preprint_183.pdf 485

This item appears in the following Collection(s)

Search KOPS


Browse

My Account