The Hierarchy in Grid Graphs

Storandt, Sabine

The Hierarchy in Grid Graphs

Files

There are no files associated with this item.

Date

2013

Authors

Storandt, Sabine

Collections

Informatik und Informationswissenschaft

Publication type

Contribution to a conference collection

Publication status

Published

Published in

Proceedings of the Sixth International Symposium on Combinatorial Search (SoCS-2013), 11 - 13 July 2013, Leavenworth, Washington, USA / Helmert, Malte (ed.). - Palo Alto, Calif. : AAAI Press, 2013. - pp. 209-210. - ISBN 978-1-57735-632-5

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.

Subject (DDC)

004 Computer Science

Keywords

route planning; grid graph; contraction hierarchies

Conference

The Sixth International Symposium on Combinatorial Search, Jul 11, 2013 - Jul 13, 2013, Leavenworth, WA, USA

Cite This

ISO 690

STORANDT, Sabine, 2013. The Hierarchy in Grid Graphs. The Sixth International Symposium on Combinatorial Search. Leavenworth, WA, USA, Jul 11, 2013 - Jul 13, 2013. In: HELMERT, Malte, ed.. Proceedings of the Sixth International Symposium on Combinatorial Search (SoCS-2013), 11 - 13 July 2013, Leavenworth, Washington, USA. Palo Alto, Calif.:AAAI Press, pp. 209-210. ISBN 978-1-57735-632-5

BibTex

@inproceedings{Storandt2013Hiera-46629,
  year={2013},
  title={The Hierarchy in Grid Graphs},
  url={https://www.aaai.org/ocs/index.php/SOCS/SOCS13/paper/view/7227},
  isbn={978-1-57735-632-5},
  publisher={AAAI Press},
  address={Palo Alto, Calif.},
  booktitle={Proceedings of the Sixth International Symposium on Combinatorial Search (SoCS-2013), 11 - 13 July 2013, Leavenworth, Washington, USA},
  pages={209--210},
  editor={Helmert, Malte},
  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/46629">
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2019-08-07T08:20:45Z</dcterms:available>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/46629"/>
    <dcterms:issued>2013</dcterms:issued>
    <dcterms:title>The Hierarchy in Grid Graphs</dcterms:title>
    <dc:creator>Storandt, Sabine</dc:creator>
    <dc:language>eng</dc:language>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <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:contributor>Storandt, Sabine</dc:contributor>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2019-08-07T08:20:45Z</dc:date>
  </rdf:Description>
</rdf:RDF>

URL of original publication

https://www.aaai.org/ocs/index.php/SOCS/SOCS13/paper/view/7227

Test date of URL

2019-05-17

Bibliography of Konstanz

No