Publikation:

The Complexity of Landmark Hub Labeling

Vorschaubild

Dateien

Zu diesem Dokument gibt es keine Dateien.

Datum

2025

Autor:innen

Coste, Louann

Herausgeber:innen

Kontakt

ISSN der Zeitschrift

Electronic ISSN

ISBN

Bibliografische Daten

Verlag

Schriftenreihe

Auflagebezeichnung

URI (zitierfähiger Link)
DOI (zitierfähiger Link)
https://doi.org/10.1007/978-3-031-92935-9_4
ArXiv-ID

Internationale Patentnummer

Angaben zur Forschungsförderung

Projekt

Open Access-Veröffentlichung

Sammlungen

Informatik und Informationswissenschaft: Publikationen
Core Facility der Universität Konstanz

Gesperrt bis

Titel in einer weiteren Sprache

Publikationstyp
Beitrag zu einem Konferenzband
Publikationsstatus
Published

Erschienen in

FINOCCHI, Irene, Hrsg., Loukas GEORGIADIS, Hrsg.. Algorithms and Complexity : 14th International Conference, CIAC 2025, Rome, Italy, June 10–12, 2025, Proceedings, Part II. Cham: Springer, 2025, S. 52-68. Lecture Notes in Computer Science (LNCS). 15680. ISSN 0302-9743. eISSN 1611-3349. ISBN 978-3-031-92934-2. Verfügbar unter: doi: 10.1007/978-3-031-92935-9_4

Zusammenfassung

To speed up the computation of shortest path distances between pairs of query nodes in a weighted graph, it is common to precompute a distance oracle. One of the most successful of these oracles is Hub Labeling (HL). Its good practical performance spurred research on the complexity of different HL variants, their structural properties, and suitable construction algorithms. Landmark Hub Labeling (LHL) is a generalization of HL. It enables the construction of distance oracles with similar query time but smaller space consumption than HL, which is an important aspect for practical usability. However, the complexity of LHL has not been thoroughly investigated so far. In this paper, we provide a complete picture of the complexity landscape of different LHL variants. Surprisingly, the only known HL variant for which a minimum-size oracle can be computed in polynomial time (namely ranked hierarchical HL) turns out to be NP-hard when generalized to LHL. We complement our hardness results with suitable approximation algorithms for all studied LHL variants based on novel structural insights.

Zusammenfassung in einer weiteren Sprache

Fachgebiet (DDC)
004 Informatik

Schlagwörter

Hub Labeling, Shortest Path, NP-Hardness

Konferenz

14th International Conference on Algorithms and Complexity : CIAC 2025, 10. Juni 2025 - 12. Juni 2025, Rome, Italy
Rezension
undefined / . - undefined, undefined

Forschungsvorhaben

Organisationseinheiten

Zeitschriftenheft

Zugehörige Datensätze in KOPS

Zitieren

ISO 690COSTE, Louann, Ruoying LI, Sabine STORANDT, Tobias TÖPFER, 2025. The Complexity of Landmark Hub Labeling. 14th International Conference on Algorithms and Complexity : CIAC 2025. Rome, Italy, 10. Juni 2025 - 12. Juni 2025. In: FINOCCHI, Irene, Hrsg., Loukas GEORGIADIS, Hrsg.. Algorithms and Complexity : 14th International Conference, CIAC 2025, Rome, Italy, June 10–12, 2025, Proceedings, Part II. Cham: Springer, 2025, S. 52-68. Lecture Notes in Computer Science (LNCS). 15680. ISSN 0302-9743. eISSN 1611-3349. ISBN 978-3-031-92934-2. Verfügbar unter: doi: 10.1007/978-3-031-92935-9_4
BibTex
@inproceedings{Coste2025Compl-74320,
  title={The Complexity of Landmark Hub Labeling},
  year={2025},
  doi={10.1007/978-3-031-92935-9_4},
  number={15680},
  isbn={978-3-031-92934-2},
  issn={0302-9743},
  address={Cham},
  publisher={Springer},
  series={Lecture Notes in Computer Science (LNCS)},
  booktitle={Algorithms and Complexity : 14th International Conference, CIAC 2025, Rome, Italy, June 10–12, 2025, Proceedings, Part II},
  pages={52--68},
  editor={Finocchi, Irene and Georgiadis, Loukas},
  author={Coste, Louann and Li, Ruoying and Storandt, Sabine and Töpfer, Tobias}
}
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/74320">
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:creator>Töpfer, Tobias</dc:creator>
    <dc:creator>Coste, Louann</dc:creator>
    <dc:contributor>Li, Ruoying</dc:contributor>
    <dcterms:abstract>To speed up the computation of shortest path distances between pairs of query nodes in a weighted graph, it is common to precompute a distance oracle. One of the most successful of these oracles is Hub Labeling (HL). Its good practical performance spurred research on the complexity of different HL variants, their structural properties, and suitable construction algorithms. Landmark Hub Labeling (LHL) is a generalization of HL. It enables the construction of distance oracles with similar query time but smaller space consumption than HL, which is an important aspect for practical usability. However, the complexity of LHL has not been thoroughly investigated so far. In this paper, we provide a complete picture of the complexity landscape of different LHL variants. Surprisingly, the only known HL variant for which a minimum-size oracle can be computed in polynomial time (namely ranked hierarchical HL) turns out to be NP-hard when generalized to LHL. We complement our hardness results with suitable approximation algorithms for all studied LHL variants based on novel structural insights.</dcterms:abstract>
    <dcterms:issued>2025</dcterms:issued>
    <dcterms:title>The Complexity of Landmark Hub Labeling</dcterms:title>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dc:language>eng</dc:language>
    <dc:contributor>Storandt, Sabine</dc:contributor>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2025-08-20T12:55:27Z</dc:date>
    <dc:creator>Li, Ruoying</dc:creator>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2025-08-20T12:55:27Z</dcterms:available>
    <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/74320"/>
    <dc:creator>Storandt, Sabine</dc:creator>
    <dc:contributor>Töpfer, Tobias</dc:contributor>
    <dc:contributor>Coste, Louann</dc:contributor>
  </rdf:Description>
</rdf:RDF>

Interner Vermerk

xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter

Kontakt
URL der Originalveröffentl.

Prüfdatum der URL

Prüfungsdatum der Dissertation

Finanzierungsart

Kommentar zur Publikation

Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Ja
Begutachtet
Diese Publikation teilen