KOPS - The Institutional Repository of the University of Konstanz

Lower Bounds and Approximation Algorithms for Search Space Sizes in Contraction Hierarchies

Lower Bounds and Approximation Algorithms for Search Space Sizes in Contraction Hierarchies

Cite This

Files in this item

Checksum: MD5:3654c214242bbf7d4172131a1e53e2fe

BLUM, Johannes, Sabine STORANDT, 2020. Lower Bounds and Approximation Algorithms for Search Space Sizes in Contraction Hierarchies. 28th Annual European Symposium on Algorithms : ESA 2020 (Virtual Conference). Pisa, Italy, Sep 7, 2020 - Sep 9, 2020. In: FABRIZIO GRANDONI, , ed., GRZEGORZ HERMAN, ed., PETER SANDERS, ed.. 28th Annual European Symposium on Algorithms : ESA 2020. Dagstuhl:Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 20. eISSN 1868-8969. ISBN 978-3-95977-162-7. Available under: doi: 10.4230/LIPIcs.ESA.2020.20

@inproceedings{Blum2020Lower-50799, title={Lower Bounds and Approximation Algorithms for Search Space Sizes in Contraction Hierarchies}, year={2020}, doi={10.4230/LIPIcs.ESA.2020.20}, number={173}, isbn={978-3-95977-162-7}, address={Dagstuhl}, publisher={Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, series={Leibniz International Proceedings in Informatics : LIPIcs}, booktitle={28th Annual European Symposium on Algorithms : ESA 2020}, editor={Fabrizio Grandoni and Grzegorz Herman and Peter Sanders}, author={Blum, Johannes and Storandt, Sabine}, note={Article Number: 20} }

<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/50799"> <dcterms:title>Lower Bounds and Approximation Algorithms for Search Space Sizes in Contraction Hierarchies</dcterms:title> <dc:rights>Attribution 3.0 Unported</dc:rights> <dc:creator>Blum, Johannes</dc:creator> <dc:language>eng</dc:language> <dc:contributor>Storandt, Sabine</dc:contributor> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2020-09-11T11:24:42Z</dcterms:available> <dc:contributor>Blum, Johannes</dc:contributor> <dc:creator>Storandt, Sabine</dc:creator> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2020-09-11T11:24:42Z</dc:date> <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/50799/1/Blum_2-7tivdcd91s0c9.pdf"/> <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/rdf/resource/123456789/36"/> <dcterms:rights rdf:resource="http://creativecommons.org/licenses/by/3.0/"/> <dcterms:issued>2020</dcterms:issued> <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/50799"/> <foaf:homepage rdf:resource="http://localhost:8080/jspui"/> <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/rdf/resource/123456789/36"/> <dcterms:abstract xml:lang="eng">Contraction hierarchies (CH) is a prominent preprocessing-based technique that accelerates the computation of shortest paths in road networks by reducing the search space size of a bidirectional Dijkstra run. To explain the practical success of CH, several theoretical upper bounds for the maximum search space size were derived in previous work. For example, it was shown that in minor-closed graph families search space sizes in 𝒪(√n) can be achieved (with n denoting the number of nodes in the graph), and search space sizes in 𝒪(h log D) in graphs of highway dimension h and diameter D. In this paper, we primarily focus on lower bounds. We prove that the average search space size in a so called weak CH is in Ω(b_α) for α ≥ 2/3 where b_α is the size of a smallest α-balanced node separator. This discovery allows us to describe the first approximation algorithm for the average search space size. Our new lower bound also shows that the 𝒪(√n) bound for minor-closed graph families is tight. Furthermore, we deeper investigate the relationship of CH and the highway dimension and skeleton dimension of the graph, and prove new lower bound and incomparability results. Finally, we discuss how lower bounds for strong CH can be obtained from solving a HittingSet problem defined on a set of carefully chosen subgraphs of the input network.</dcterms:abstract> <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/50799/1/Blum_2-7tivdcd91s0c9.pdf"/> </rdf:Description> </rdf:RDF>

Downloads since Sep 11, 2020 (Information about access statistics)

Blum_2-7tivdcd91s0c9.pdf 107

This item appears in the following Collection(s)

Attribution 3.0 Unported Except where otherwise noted, this item's license is described as Attribution 3.0 Unported

Search KOPS


My Account