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

Zitieren

Dateien zu dieser Ressource

Prüfsumme: 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:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" xmlns:bibo="http://purl.org/ontology/bibo/" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:dcterms="http://purl.org/dc/terms/" 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> <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:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T16:11:29Z</dc:date> <dc:contributor>Willhalm, Thomas</dc:contributor> <dc:contributor>Wagner, Dorothea</dc:contributor> <dc:language>eng</dc:language> <dc:creator>Wagner, Dorothea</dc:creator> <dc:rights>deposit-license</dc:rights> <dcterms:issued>2003</dcterms:issued> <dcterms:rights rdf:resource="http://nbn-resolving.org/urn:nbn:de:bsz:352-20140905103416863-3868037-7"/> <dc:format>application/pdf</dc:format> <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/6328"/> </rdf:Description> </rdf:RDF>

Dateiabrufe seit 01.10.2014 (Informationen über die Zugriffsstatistik)

preprint_183.pdf 210

Das Dokument erscheint in:

KOPS Suche


Stöbern

Mein Benutzerkonto