The Hierarchy in Grid Graphs

Storandt, Sabine

The Hierarchy in Grid Graphs

Dateien

Zu diesem Dokument gibt es keine Dateien.

Datum

2013

Autor:innen

Storandt, Sabine

Sammlungen

Informatik und Informationswissenschaft

Publikationstyp

Beitrag zu einem Konferenzband

Publikationsstatus

Published

Erschienen 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, 2013, pp. 209-210. ISBN 978-1-57735-632-5

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.

Fachgebiet (DDC)

004 Informatik

Schlagwörter

route planning; grid graph; contraction hierarchies

Konferenz

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

Zitieren

ISO 690

STORANDT, Sabine, 2013. The Hierarchy in Grid Graphs. The Sixth International Symposium on Combinatorial Search. Leavenworth, WA, USA, 11. Juli 2013 - 13. Juli 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, 2013, 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 der Originalveröffentl.

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

Prüfdatum der URL

2019-05-17

Universitätsbibliographie

Nein