Publikation: Customizable Hub Labeling : Properties and Algorithms
Dateien
Datum
Autor:innen
Herausgeber:innen
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
DOI (zitierfähiger Link)
Internationale Patentnummer
Angaben zur Forschungsförderung
Projekt
Open Access-Veröffentlichung
Core Facility der Universität Konstanz
Titel in einer weiteren Sprache
Publikationstyp
Publikationsstatus
Erschienen in
Zusammenfassung
Hub Labeling (HL) is a state-of-the-art preprocessing-based technique for route planning in road networks. It is a special incarnation of distance labeling, and it is well-studied in both theory and practice. The core concept of HL is to associate a label with each vertex, which consists of a subset of all vertices and respective shortest path information, such that the shortest path distance between any two vertices can be derived from considering the intersection of their labels. HL provides excellent query times but requires a time-consuming preprocessing phase. Therefore, in case of edge cost changes, rerunning the whole preprocessing is not viable. Inspired by the concept of Customizable Route Planning, we hence propose in this paper a Customizable Hub Labeling variant for which the edge costs in the network do not need to be known at construction time. These labels can then be used with any edge costs after conducting a so called customization phase. We study the theoretical properties of Customizable Hub Labelings, provide an O(log2n)-approximation algorithm for the average label size, and propose efficient customization algorithms.
Zusammenfassung in einer weiteren Sprache
Fachgebiet (DDC)
Schlagwörter
Konferenz
Rezension
Zitieren
ISO 690
BLUM, Johannes, Sabine STORANDT, 2022. Customizable Hub Labeling : Properties and Algorithms. Computing and Combinatorics - 28th International Conference, COCOON 2022. Shenzhen, China, 22. Okt. 2022 - 24. Okt. 2022. In: ZHANG, Yong, ed., Dongjing MIAO, ed., Rolf MÖHRING, ed.. Computing and Combinatorics : 28th International Conference, COCOON 2022, Proceedings. Cham: Springer, 2022, pp. 345-356. Lecture Notes in Computer Science. 13595. Available under: doi: 10.1007/978-3-031-22105-7\_31BibTex
@inproceedings{Blum2022Custo-59727, year={2022}, doi={10.1007/978-3-031-22105-7\_31}, title={Customizable Hub Labeling : Properties and Algorithms}, number={13595}, publisher={Springer}, address={Cham}, series={Lecture Notes in Computer Science}, booktitle={Computing and Combinatorics : 28th International Conference, COCOON 2022, Proceedings}, pages={345--356}, editor={Zhang, Yong and Miao, Dongjing and Möhring, Rolf}, author={Blum, Johannes and Storandt, Sabine} }
RDF
<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/59727"> <dc:contributor>Blum, Johannes</dc:contributor> <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/59727"/> <dcterms:title>Customizable Hub Labeling : Properties and Algorithms</dcterms:title> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2023-01-16T12:18:46Z</dc:date> <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/> <dcterms:abstract xml:lang="eng">Hub Labeling (HL) is a state-of-the-art preprocessing-based technique for route planning in road networks. It is a special incarnation of distance labeling, and it is well-studied in both theory and practice. The core concept of HL is to associate a label with each vertex, which consists of a subset of all vertices and respective shortest path information, such that the shortest path distance between any two vertices can be derived from considering the intersection of their labels. HL provides excellent query times but requires a time-consuming preprocessing phase. Therefore, in case of edge cost changes, rerunning the whole preprocessing is not viable. Inspired by the concept of Customizable Route Planning, we hence propose in this paper a Customizable Hub Labeling variant for which the edge costs in the network do not need to be known at construction time. These labels can then be used with any edge costs after conducting a so called customization phase. We study the theoretical properties of Customizable Hub Labelings, provide an O(log<sup>2</sup>n)-approximation algorithm for the average label size, and propose efficient customization algorithms.</dcterms:abstract> <dc:contributor>Storandt, Sabine</dc:contributor> <dc:creator>Blum, Johannes</dc:creator> <foaf:homepage rdf:resource="http://localhost:8080/"/> <dc:rights>terms-of-use</dc:rights> <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/> <dcterms:issued>2022</dcterms:issued> <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2023-01-16T12:18:46Z</dcterms:available> <dc:language>eng</dc:language> <dc:creator>Storandt, Sabine</dc:creator> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> </rdf:Description> </rdf:RDF>