Publikation: Contraction Hierarchies on Grid Graphs
Lade...
Dateien
Zu diesem Dokument gibt es keine Dateien.
Datum
2013
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
Beitrag zu einem Konferenzband
Publikationsstatus
Published
Erschienen in
TIMM, Ingo J., ed. and others. KI 2013: Advances in Artificial Intelligence : 36th Annual German Conference on AI, Koblenz, Germany, September 16-20, 2013, Proceedings. Berlin: Springer, 2013, pp. 236-247. Lecture Notes in Artificial Intelligence. 8077. ISSN 0302-9743. eISSN 1611-3349. ISBN 978-3-642-40941-7. Available under: doi: 10.1007/978-3-642-40942-4_21
Zusammenfassung
Many speed-up techniques developed for accelerating the computation of shortest paths in road networks, like reach or contraction hierarchies, are based on the property that some streets are ’more important’ than others, e.g. on long routes the usage of an interstate is almost inevitable. In grids there is no obvious hierarchy among the edges, especially if the costs are uniform. Nevertheless we will show that contraction hierarchies can be applied to grid graphs as well. We will point out interesting connections to speed-up techniques shaped for routing on grids, like swamp hierarchies and jump points, and provide experimental results for game maps, mazes, random grids and rooms.
Zusammenfassung in einer weiteren Sprache
Fachgebiet (DDC)
004 Informatik
Schlagwörter
Short Path, Road Network, Optimal Path, Grid Graph, Jump Point
Konferenz
36th Annual German Conference on AI (KI 2013), 16. Sept. 2013 - 20. Sept. 2013, Koblenz, Germany
Rezension
undefined / . - undefined, undefined
Zitieren
ISO 690
STORANDT, Sabine, 2013. Contraction Hierarchies on Grid Graphs. 36th Annual German Conference on AI (KI 2013). Koblenz, Germany, 16. Sept. 2013 - 20. Sept. 2013. In: TIMM, Ingo J., ed. and others. KI 2013: Advances in Artificial Intelligence : 36th Annual German Conference on AI, Koblenz, Germany, September 16-20, 2013, Proceedings. Berlin: Springer, 2013, pp. 236-247. Lecture Notes in Artificial Intelligence. 8077. ISSN 0302-9743. eISSN 1611-3349. ISBN 978-3-642-40941-7. Available under: doi: 10.1007/978-3-642-40942-4_21BibTex
@inproceedings{Storandt2013Contr-45892,
year={2013},
doi={10.1007/978-3-642-40942-4_21},
title={Contraction Hierarchies on Grid Graphs},
number={8077},
isbn={978-3-642-40941-7},
issn={0302-9743},
publisher={Springer},
address={Berlin},
series={Lecture Notes in Artificial Intelligence},
booktitle={KI 2013: Advances in Artificial Intelligence : 36th Annual German Conference on AI, Koblenz, Germany, September 16-20, 2013, Proceedings},
pages={236--247},
editor={Timm, Ingo J.},
author={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/45892">
<dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
<dcterms:issued>2013</dcterms:issued>
<foaf:homepage rdf:resource="http://localhost:8080/"/>
<dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2019-05-23T08:54:42Z</dc:date>
<dc:contributor>Storandt, Sabine</dc:contributor>
<void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
<dcterms:abstract xml:lang="eng">Many speed-up techniques developed for accelerating the computation of shortest paths in road networks, like reach or contraction hierarchies, are based on the property that some streets are ’more important’ than others, e.g. on long routes the usage of an interstate is almost inevitable. In grids there is no obvious hierarchy among the edges, especially if the costs are uniform. Nevertheless we will show that contraction hierarchies can be applied to grid graphs as well. We will point out interesting connections to speed-up techniques shaped for routing on grids, like swamp hierarchies and jump points, and provide experimental results for game maps, mazes, random grids and rooms.</dcterms:abstract>
<dc:language>eng</dc:language>
<dcterms:title>Contraction Hierarchies on Grid Graphs</dcterms:title>
<bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/45892"/>
<dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2019-05-23T08:54:42Z</dcterms:available>
<dc:creator>Storandt, Sabine</dc:creator>
<dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
</rdf:Description>
</rdf:RDF>Interner Vermerk
xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter
Prüfungsdatum der Dissertation
Finanzierungsart
Kommentar zur Publikation
Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Nein
