Generierung und Abdeckung repräsentativer Pfadmengen in Straßennetzwerken
| dc.contributor.author | Berner, Lukas | |
| dc.contributor.editor | Gesellschaft für Informatik e.V. | |
| dc.date.accessioned | 2023-02-21T09:39:16Z | |
| dc.date.available | 2023-02-21T09:39:16Z | |
| dc.date.issued | 2022 | |
| dc.description.abstract | Für die Suche nach kürzesten Pfaden in sehr großen Graphen wurden verschiedene Beschleunigungstechniken, wie z.B. Contraction Hierarchies, Hub-Labels oder Transit Node Routing, entwickelt. Um optimale Anfragezeiten und Speicherverbrauch zu erreichen, benötigen viele Beschleunigungstechniken eine Menge wichtiger Knoten. In dieser Arbeit wird eine Methode zur Berechnung wichtiger Knoten eines Graphen vorgestellt. Um diese Knoten zu finden, wird auf einer repräsentativen Pfadmenge ein Hitting Set Problem mit einem Greedy-Algorithmus gelöst. Die repräsentative Pfadmenge, die möglichst unterschiedliche kürzeste Pfade des Graphen enthalten soll, wird mit einer well-separated pair decomposition und einem Quadtree berechnet. Das Verfahren wurde mit dem deutschen Straßennetzwerk (25M Knoten) getestet und liefert hier einige tausend wichtige Knoten, mit denen bereits etwa 99.9% aller kürzesten Pfade im Graph abgedeckt sind. | de |
| dc.identifier.isbn | 978-3-88579-752-4 | |
| dc.identifier.pissn | 1614-3213 | |
| dc.identifier.uri | https://dl.gi.de/handle/20.500.12116/40230 | |
| dc.language.iso | de | |
| dc.publisher | Gesellschaft für Informatik, Bonn | |
| dc.relation.ispartof | SKILL 2022 | |
| dc.relation.ispartofseries | Lecture Notes in Informatics (LNI) - Seminars, Volume S-18 | |
| dc.subject | Kürzeste Wege | |
| dc.subject | Straßennetzwerke | |
| dc.subject | Well-Separated Pair Decomposition | |
| dc.subject | Greedy Hitting Set | |
| dc.title | Generierung und Abdeckung repräsentativer Pfadmengen in Straßennetzwerken | de |
| gi.citation.endPage | 22 | |
| gi.citation.startPage | 11 | |
| gi.conference.date | 29.-30. September 2022 | |
| gi.conference.location | Hamburg | |
| gi.conference.sessiontitle | Routenberechnung |
Dateien
Originalbündel
1 - 1 von 1