Bitte benutzen Sie diese Kennung, um auf die Ressource zu verweisen:
http://dx.doi.org/10.18419/opus-12857
Autor(en): | Rupp, Tobias Funke, Stefan |
Titel: | A lower bound for the query phase of contraction hierarchies and hub labels and a provably optimal instance-based schema |
Erscheinungsdatum: | 2021 |
Dokumentart: | Zeitschriftenartikel |
Seiten: | 19 |
Erschienen in: | Algorithms 14 (2021), No. 164 |
URI: | http://nbn-resolving.de/urn:nbn:de:bsz:93-opus-ds-128767 http://elib.uni-stuttgart.de/handle/11682/12876 http://dx.doi.org/10.18419/opus-12857 |
ISSN: | 1999-4893 |
Zusammenfassung: | We prove a Ω(√n) lower bound on the query time for contraction hierarchies (CH) as well as hub labels, two popular speed-up techniques for shortest path routing. Our construction is based on a graph family not too far from subgraphs that occur in real-world road networks, in particular, it is planar and has a bounded degree. Additionally, we borrow ideas from our lower bound proof to come up with instance-based lower bounds for concrete road network instances of moderate size, reaching up to 96% of an upper bound given by a constructed CH. For a variant of our instance-based schema applied to some special graph classes, we can even show matching upper and lower bounds. |
Enthalten in den Sammlungen: | 05 Fakultät Informatik, Elektrotechnik und Informationstechnik |
Dateien zu dieser Ressource:
Datei | Beschreibung | Größe | Format | |
---|---|---|---|---|
algorithms-14-00164-v2.pdf | 3,27 MB | Adobe PDF | Öffnen/Anzeigen |
Diese Ressource wurde unter folgender Copyright-Bestimmung veröffentlicht: Lizenz von Creative Commons