Hierarchical speed-up techniques for shortest-path algorithms
Hierarchical speed-up techniques for shortest-path algorithms
Loading...
Date
2003
Authors
Holzer, Martin
Editors
Journal ISSN
Electronic ISSN
ISBN
Bibliographical data
Publisher
Series
URI (citable link)
International patent number
Link to the license
EU project number
Project
Open Access publication
Collections
Title in another language
Publication type
Diploma thesis
Publication status
Published in
Abstract
Shortest-path problems occur in many fields of application, where the graphs are often
very large and queries have to be answered in 'real-time'. This cannot be overcome by the
classical algorithm of Dijkstra but requires more sophisticated speed-up techniques. One approach
consists of hierarchical decomposition of a given graph and pre-computation of information in order
to reduce search space during the on-line stage.
One such technique applied to a specific scenario was recently investigated in a systematic
experimental study. In the following work, we follow up and give a detailed analysis of this speed-up technique along with experiments using several graph classes.
very large and queries have to be answered in 'real-time'. This cannot be overcome by the
classical algorithm of Dijkstra but requires more sophisticated speed-up techniques. One approach
consists of hierarchical decomposition of a given graph and pre-computation of information in order
to reduce search space during the on-line stage.
One such technique applied to a specific scenario was recently investigated in a systematic
experimental study. In the following work, we follow up and give a detailed analysis of this speed-up technique along with experiments using several graph classes.
Summary in another language
Subject (DDC)
004 Computer Science
Keywords
hierarchisch,kürzest,Verschnellerung,Beschleunigungstechnik,algorithm,speed-up,graph,path,shortest
Conference
Review
undefined / . - undefined, undefined. - (undefined; undefined)
Cite This
ISO 690
HOLZER, Martin, 2003. Hierarchical speed-up techniques for shortest-path algorithms [Master thesis]BibTex
@mastersthesis{Holzer2003Hiera-6098,
year={2003},
title={Hierarchical speed-up techniques for shortest-path algorithms},
author={Holzer, Martin}
}
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/6098">
<dc:rights>terms-of-use</dc:rights>
<dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
<bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/6098"/>
<dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
<dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/6098/1/da_finished.pdf"/>
<void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
<dc:contributor>Holzer, Martin</dc:contributor>
<dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T16:09:32Z</dc:date>
<dcterms:title>Hierarchical speed-up techniques for shortest-path algorithms</dcterms:title>
<foaf:homepage rdf:resource="http://localhost:8080/"/>
<dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/6098/1/da_finished.pdf"/>
<dcterms:abstract xml:lang="eng">Shortest-path problems occur in many fields of application, where the graphs are often<br />very large and queries have to be answered in 'real-time'. This cannot be overcome by the<br />classical algorithm of Dijkstra but requires more sophisticated speed-up techniques. One approach<br />consists of hierarchical decomposition of a given graph and pre-computation of information in order<br />to reduce search space during the on-line stage.<br /><br />One such technique applied to a specific scenario was recently investigated in a systematic<br />experimental study. In the following work, we follow up and give a detailed analysis of this speed-up technique along with experiments using several graph classes.</dcterms:abstract>
<dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/>
<dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T16:09:32Z</dcterms:available>
<dc:format>application/pdf</dc:format>
<dc:language>eng</dc:language>
<dcterms:issued>2003</dcterms:issued>
<dc:creator>Holzer, Martin</dc:creator>
</rdf:Description>
</rdf:RDF>