KOPS - The Institutional Repository of the University of Konstanz

Sublinear Search Spaces for Shortest Path Planning in Grid and Road Networks

Sublinear Search Spaces for Shortest Path Planning in Grid and Road Networks

Cite This

Files in this item

Checksum: MD5:f4f59eb1a1f9314fa3c60a0ee51bf180

BLUM, Johannes, Stefan FUNKE, Sabine STORANDT, 2021. Sublinear Search Spaces for Shortest Path Planning in Grid and Road Networks. In: Journal of Combinatorial Optimization. Springer. 42(2), pp. 231-257. ISSN 1382-6905. eISSN 1573-2886. Available under: doi: 10.1007/s10878-021-00777-3

@article{Blum2021-08Subli-44520.2, title={Sublinear Search Spaces for Shortest Path Planning in Grid and Road Networks}, year={2021}, doi={10.1007/s10878-021-00777-3}, number={2}, volume={42}, issn={1382-6905}, journal={Journal of Combinatorial Optimization}, pages={231--257}, author={Blum, Johannes and Funke, Stefan and Storandt, Sabine} }

<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/44520.2"> <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/44520.2/1/Blum_2-azmjbiivodmm5.pdf"/> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2021-08-05T11:13:09Z</dc:date> <dc:creator>Blum, Johannes</dc:creator> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/44520.2/1/Blum_2-azmjbiivodmm5.pdf"/> <dc:contributor>Blum, Johannes</dc:contributor> <dcterms:title>Sublinear Search Spaces for Shortest Path Planning in Grid and Road Networks</dcterms:title> <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/rdf/resource/123456789/36"/> <dc:rights>terms-of-use</dc:rights> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2021-08-05T11:13:09Z</dcterms:available> <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/rdf/resource/123456789/36"/> <dcterms:abstract xml:lang="eng">Shortest path planning is a fundamental building block in many applications. Hence developing efficient methods for computing shortest paths in, e.g., road or grid networks is an important challenge. The most successful techniques for fast query answering rely on preprocessing. However, for many of these techniques it is not fully understood why they perform so remarkably well, and theoretical justification for the empirical results is missing. An attempt to explain the excellent practical performance of preprocessing based techniques on road networks (as transit nodes, hub labels, or contraction hierarchies) in a sound theoretical way are parametrized analyses, e.g., considering the highway dimension or skeleton dimension of a graph. Still, these parameters may be large in case the network contains grid-like substructures—which inarguably is the case for real-world road networks around the globe. In this paper, we use the very intuitive notion of bounded growth graphs to describe road networks and also grid graphs. We show that this model suffices to prove sublinear search spaces for the three above mentioned state-of-the-art shortest path planning techniques. Furthermore, our preprocessing methods are close to the ones used in practice and only require expected polynomial time.</dcterms:abstract> <dc:creator>Funke, Stefan</dc:creator> <dc:language>eng</dc:language> <dc:contributor>Funke, Stefan</dc:contributor> <dcterms:issued>2021-08</dcterms:issued> <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/44520.2"/> <foaf:homepage rdf:resource="http://localhost:8080/jspui"/> <dc:creator>Storandt, Sabine</dc:creator> <dc:contributor>Storandt, Sabine</dc:contributor> <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/> </rdf:Description> </rdf:RDF>

Downloads since Aug 5, 2021 (Information about access statistics)

Blum_2-azmjbiivodmm5.pdf 4

This item appears in the following Collection(s)

Version History

Version Item Date Summary Publication Version

*Selected version

Search KOPS


Browse

My Account