Computation and Growth of Road Network Dimensions

Cite This

Files in this item

Files Size Format View

There are no files associated with this item.

BLUM, Johannes, Sabine STORANDT, 2018. Computation and Growth of Road Network Dimensions. 24th International Conference, COCOON 2018. Qing Dao, China, Jul 2, 2018 - Jul 4, 2018. In: WANG, Lusheng, ed. and others. Computation and Growth of Road Network Dimensions, 24th International Conference, COCOON 2018, Qing Dao, China, July 2-4, 2018, proceedings. Cham:Springer, pp. 230-241. ISSN 0302-9743. eISSN 1611-3349. ISBN 978-3-319-94775-4. Available under: doi: 10.1007/978-3-319-94776-1_20

@inproceedings{Blum2018Compu-43344, title={Computation and Growth of Road Network Dimensions}, year={2018}, doi={10.1007/978-3-319-94776-1_20}, number={10976}, isbn={978-3-319-94775-4}, issn={0302-9743}, address={Cham}, publisher={Springer}, series={Lecture Notes in Computer Science}, booktitle={Computation and Growth of Road Network Dimensions, 24th International Conference, COCOON 2018, Qing Dao, China, July 2-4, 2018, proceedings}, pages={230--241}, editor={Wang, Lusheng}, author={Blum, Johannes and Storandt, Sabine} }

<rdf:RDF xmlns:dcterms="" xmlns:dc="" xmlns:rdf="" xmlns:bibo="" xmlns:dspace="" xmlns:foaf="" xmlns:void="" xmlns:xsd="" > <rdf:Description rdf:about=""> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dc:contributor>Storandt, Sabine</dc:contributor> <dcterms:isPartOf rdf:resource=""/> <dc:creator>Storandt, Sabine</dc:creator> <dcterms:abstract xml:lang="eng">There is a plethora of route planning techniques which work remarkably well on real-world road networks. To explain their good performance, theoretical bounds in dependency of road network parameters as the highway dimension h or the skeleton dimension k were investigated. For example, for the hub label technique, query times in the order of O(plogD) and a space consumption of O(nplogD) were proven for both p=h and p=k, with D denoting the graph diameter and n the number of nodes in the network. But these bounds are only meaningful when the dimension values h or k are known. While it was conjectured that h and k grow polylogarithmically in n, their true nature was not thoroughly investigated before – primarily because of a lack of efficient algorithms for their computation. For the highway dimension, this is especially challenging as it is NP-hard to decide whether a network has highway dimension at most h. We describe the first efficient algorithms to lower bound the highway dimension and to compute the skeleton dimension exactly, even in huge networks. This allows us to formulate new conjectures about their growth behavior. Somewhat surprisingly, our results imply that h and k scale very differently. While k turns out to be a constant, we expect h to grow superpolylogarithmically in n. These observations have implications for the future design and analysis of route planning techniques.</dcterms:abstract> <dc:contributor>Blum, Johannes</dc:contributor> <dc:language>eng</dc:language> <foaf:homepage rdf:resource="http://localhost:8080/jspui"/> <dspace:isPartOfCollection rdf:resource=""/> <dc:date rdf:datatype="">2018-09-20T13:30:42Z</dc:date> <dcterms:issued>2018</dcterms:issued> <dcterms:available rdf:datatype="">2018-09-20T13:30:42Z</dcterms:available> <dcterms:title>Computation and Growth of Road Network Dimensions</dcterms:title> <dc:creator>Blum, Johannes</dc:creator> <bibo:uri rdf:resource=""/> </rdf:Description> </rdf:RDF>

This item appears in the following Collection(s)

Search KOPS


My Account