Bitte benutzen Sie diese Kennung, um auf die Ressource zu verweisen:
http://dx.doi.org/10.18419/opus-12857
Langanzeige der Metadaten
DC Element | Wert | Sprache |
---|---|---|
dc.contributor.author | Rupp, Tobias | - |
dc.contributor.author | Funke, Stefan | - |
dc.date.accessioned | 2023-03-30T12:12:28Z | - |
dc.date.available | 2023-03-30T12:12:28Z | - |
dc.date.issued | 2021 | - |
dc.identifier.issn | 1999-4893 | - |
dc.identifier.other | 1843172968 | - |
dc.identifier.uri | http://nbn-resolving.de/urn:nbn:de:bsz:93-opus-ds-128767 | de |
dc.identifier.uri | http://elib.uni-stuttgart.de/handle/11682/12876 | - |
dc.identifier.uri | http://dx.doi.org/10.18419/opus-12857 | - |
dc.description.abstract | 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. | en |
dc.language.iso | en | de |
dc.relation.uri | doi:10.3390/a14060164 | de |
dc.rights | info:eu-repo/semantics/openAccess | de |
dc.rights.uri | https://creativecommons.org/licenses/by/4.0/ | de |
dc.subject.ddc | 004 | de |
dc.subject.ddc | 380 | de |
dc.title | A lower bound for the query phase of contraction hierarchies and hub labels and a provably optimal instance-based schema | en |
dc.type | article | de |
dc.date.updated | 2021-06-12T05:15:24Z | - |
ubs.fakultaet | Informatik, Elektrotechnik und Informationstechnik | de |
ubs.institut | Institut für Formale Methoden der Informatik | de |
ubs.publikation.seiten | 19 | de |
ubs.publikation.source | Algorithms 14 (2021), No. 164 | de |
ubs.publikation.typ | Zeitschriftenartikel | de |
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