Contraction Hierarchies on Grid Graphs
| dc.contributor.author | Storandt, Sabine | |
| dc.date.accessioned | 2019-05-23T08:54:42Z | |
| dc.date.available | 2019-05-23T08:54:42Z | |
| dc.date.issued | 2013 | eng |
| dc.description.abstract | 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. | eng |
| dc.description.version | published | eng |
| dc.identifier.doi | 10.1007/978-3-642-40942-4_21 | eng |
| dc.identifier.uri | https://kops.uni-konstanz.de/handle/123456789/45892 | |
| dc.language.iso | eng | eng |
| dc.subject | Short Path, Road Network, Optimal Path, Grid Graph, Jump Point | eng |
| dc.subject.ddc | 004 | eng |
| dc.title | Contraction Hierarchies on Grid Graphs | eng |
| dc.type | INPROCEEDINGS | eng |
| dspace.entity.type | Publication | |
| kops.citation.bibtex | @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}
} | |
| kops.citation.iso690 | 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_21 | deu |
| kops.citation.iso690 | STORANDT, Sabine, 2013. Contraction Hierarchies on Grid Graphs. 36th Annual German Conference on AI (KI 2013). Koblenz, Germany, Sep 16, 2013 - Sep 20, 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_21 | eng |
| kops.citation.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> | |
| kops.conferencefield | 36th Annual German Conference on AI (KI 2013), 16. Sept. 2013 - 20. Sept. 2013, Koblenz, Germany | deu |
| kops.date.conferenceEnd | 2013-09-20 | eng |
| kops.date.conferenceStart | 2013-09-16 | eng |
| kops.flag.knbibliography | false | |
| kops.location.conference | Koblenz, Germany | eng |
| kops.sourcefield | TIMM, Ingo J., ed. and others. <i>KI 2013: Advances in Artificial Intelligence : 36th Annual German Conference on AI, Koblenz, Germany, September 16-20, 2013, Proceedings</i>. 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 | deu |
| kops.sourcefield.plain | 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 | deu |
| kops.sourcefield.plain | 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 | eng |
| kops.title.conference | 36th Annual German Conference on AI (KI 2013) | eng |
| relation.isAuthorOfPublication | a3ac49b1-8947-4bb2-840c-50a5cb77fdf4 | |
| relation.isAuthorOfPublication.latestForDiscovery | a3ac49b1-8947-4bb2-840c-50a5cb77fdf4 | |
| source.bibliographicInfo.fromPage | 236 | eng |
| source.bibliographicInfo.seriesNumber | 8077 | eng |
| source.bibliographicInfo.toPage | 247 | eng |
| source.contributor.editor | Timm, Ingo J. | |
| source.flag.etalEditor | true | eng |
| source.identifier.eissn | 1611-3349 | eng |
| source.identifier.isbn | 978-3-642-40941-7 | eng |
| source.identifier.issn | 0302-9743 | eng |
| source.publisher | Springer | eng |
| source.publisher.location | Berlin | eng |
| source.relation.ispartofseries | Lecture Notes in Artificial Intelligence | eng |
| source.title | KI 2013: Advances in Artificial Intelligence : 36th Annual German Conference on AI, Koblenz, Germany, September 16-20, 2013, Proceedings | eng |