Finding k-Dissimilar Paths with Minimum Collective Length

Cite This

Files in this item

Files Size Format View

There are no files associated with this item.

CHONDROGIANNIS, Theodoros, Panagiotis BOUROS, Johann GAMPER, Ulf LESER, David B. BLUMENTHAL, 2018. Finding k-Dissimilar Paths with Minimum Collective Length. The 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems : SIGSPATIAL '18. Seattle, Washington, Nov 6, 2018 - Nov 9, 2018. In: Proceedings of the 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York, NY:ACM Press, pp. 404-407. ISBN 978-1-4503-5889-7. Available under: doi: 10.1145/3274895.3274903

@inproceedings{Chondrogiannis2018-09-18Findi-44861, title={Finding k-Dissimilar Paths with Minimum Collective Length}, year={2018}, doi={10.1145/3274895.3274903}, isbn={978-1-4503-5889-7}, address={New York, NY}, publisher={ACM Press}, booktitle={Proceedings of the 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems}, pages={404--407}, author={Chondrogiannis, Theodoros and Bouros, Panagiotis and Gamper, Johann and Leser, Ulf and Blumenthal, David B.} }

<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/rdf/resource/123456789/44861"> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dc:creator>Blumenthal, David B.</dc:creator> <dc:creator>Gamper, Johann</dc:creator> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2019-02-05T13:46:33Z</dcterms:available> <dc:creator>Leser, Ulf</dc:creator> <dc:creator>Chondrogiannis, Theodoros</dc:creator> <dc:contributor>Gamper, Johann</dc:contributor> <dc:contributor>Chondrogiannis, Theodoros</dc:contributor> <dcterms:issued>2018-09-18</dcterms:issued> <dc:contributor>Bouros, Panagiotis</dc:contributor> <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/rdf/resource/123456789/36"/> <dc:creator>Bouros, Panagiotis</dc:creator> <dcterms:abstract xml:lang="eng">Shortest path computation is a fundamental problem in road networks. However, in many real-world scenarios, determining solely the shortest path is not enough. In this paper, we study the problem of finding k-Dissimilar Paths with Minimum Collective Length (kDPwML), which aims at computing a set of paths from a source s to a target t such that all paths are pairwise dissimilar by at least θ and the sum of the path lengths is minimal. We introduce an exact algorithm for the kDPwML problem, which iterates over all possible s-t paths while employing two pruning techniques to reduce the prohibitively expensive computational cost. To achieve scalability, we also define the much smaller set of the simple single-via paths, and we adapt two algorithms for kDPwML queries to iterate over this set. Our experimental analysis on real road networks shows that iterating over all paths is impractical, while iterating over the set of simple single-via paths can lead to scalable solutions with only a small trade-off in the quality of the results.</dcterms:abstract> <dc:language>eng</dc:language> <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/rdf/resource/123456789/36"/> <foaf:homepage rdf:resource="http://localhost:8080/jspui"/> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2019-02-05T13:46:33Z</dc:date> <dc:contributor>Leser, Ulf</dc:contributor> <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/44861"/> <dc:contributor>Blumenthal, David B.</dc:contributor> <dcterms:title>Finding k-Dissimilar Paths with Minimum Collective Length</dcterms:title> </rdf:Description> </rdf:RDF>

This item appears in the following Collection(s)

Search KOPS


Browse

My Account