@inproceedings{Blum2020Lower-50799,
  year={2020},
  doi={10.4230/LIPIcs.ESA.2020.20},
  title={Lower Bounds and Approximation Algorithms for Search Space Sizes in Contraction Hierarchies},
  number={173},
  isbn={978-3-95977-162-7},
  publisher={Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  address={Dagstuhl},
  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/server/rdf/resource/123456789/50799">
    <dcterms:issued>2020</dcterms:issued>
    <dcterms:title>Lower Bounds and Approximation Algorithms for Search Space Sizes in Contraction Hierarchies</dcterms:title>
    <dc:creator>Blum, Johannes</dc:creator>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dc:language>eng</dc:language>
    <dcterms:rights rdf:resource="http://creativecommons.org/licenses/by/3.0/"/>
    <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/50799/1/Blum_2-7tivdcd91s0c9.pdf"/>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:rights>Attribution 3.0 Unported</dc:rights>
    <dc:contributor>Blum, Johannes</dc:contributor>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/50799/1/Blum_2-7tivdcd91s0c9.pdf"/>
    <dc:creator>Storandt, Sabine</dc:creator>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2020-09-11T11:24:42Z</dc:date>
    <dc:contributor>Storandt, Sabine</dc:contributor>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2020-09-11T11:24:42Z</dcterms:available>
    <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>
    <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/50799"/>
  </rdf:Description>
</rdf:RDF>