Concatenated k-Path Covers

Cite This

Files in this item

Files Size Format View

There are no files associated with this item.

BECK, Moritz, Kam-Yiu LAM, Joseph Kee Yin NG, Sabine STORANDT, Chun Jiang ZHU, 2019. Concatenated k-Path Covers. The Twenty-First Workshop on Algorithm Engineering and Experiments (ALENEX). San Diego, California, Jan 7, 2019 - Jan 8, 2019. In: KOBOUROV, Stephen, ed., Henning MEYERHENKE, ed.. 2019 Proceedings of the Twenty-First Workshop on Algorithm Engineering and Experiments (ALENEX). Philadelphia, PA:SIAM, pp. 81-91. ISBN 978-1-61197-549-9. Available under: doi: 10.1137/1.9781611975499.7

@inproceedings{Beck2019-01-02Conca-44521, title={Concatenated k-Path Covers}, year={2019}, doi={10.1137/1.9781611975499.7}, isbn={978-1-61197-549-9}, address={Philadelphia, PA}, publisher={SIAM}, booktitle={2019 Proceedings of the Twenty-First Workshop on Algorithm Engineering and Experiments (ALENEX)}, pages={81--91}, editor={Kobourov, Stephen and Meyerhenke, Henning}, author={Beck, Moritz and Lam, Kam-Yiu and Ng, Joseph Kee Yin and Storandt, Sabine and Zhu, Chun Jiang} }

<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/44521"> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dc:contributor>Ng, Joseph Kee Yin</dc:contributor> <dc:contributor>Zhu, Chun Jiang</dc:contributor> <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/rdf/resource/123456789/36"/> <dc:creator>Lam, Kam-Yiu</dc:creator> <dcterms:title>Concatenated k-Path Covers</dcterms:title> <dc:language>eng</dc:language> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2019-01-10T15:18:05Z</dcterms:available> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2019-01-10T15:18:05Z</dc:date> <dc:creator>Beck, Moritz</dc:creator> <dc:contributor>Beck, Moritz</dc:contributor> <dc:creator>Zhu, Chun Jiang</dc:creator> <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/44521"/> <dc:creator>Ng, Joseph Kee Yin</dc:creator> <dcterms:issued>2019-01-02</dcterms:issued> <foaf:homepage rdf:resource="http://localhost:8080/jspui"/> <dc:contributor>Storandt, Sabine</dc:contributor> <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/rdf/resource/123456789/36"/> <dc:contributor>Lam, Kam-Yiu</dc:contributor> <dc:creator>Storandt, Sabine</dc:creator> <dcterms:abstract xml:lang="eng">Given a directed graph G(V,E), a k-(Shortest) Path Cover is a subset C of the nodes V such that every simple (or shortest) path in G consisting of k nodes contains at least one node from C. In this paper, we extend the notion of k-Path Covers such that the objects to be covered don't have to be single paths but can be concatenations of up to p simple (or shortest) paths. For the generalized problem of computing concatenated k-(Shortest) Path Covers, we present theoretical results regarding the VC-dimension of the concatenated path set in dependency of p as well as (approximation) algorithms. Subsequently, we study interesting special cases of concatenated k-Path Covers, in particular, covers for piecewise shortest paths, round tours and trees. For those, we show how the pruning algorithm for k-Path Cover computation can be abstracted and modified in order to also solve concatenated k-Path Cover problems. An extensive experimental study on different graph types proves the applicability and efficiency of our approaches.</dcterms:abstract> </rdf:Description> </rdf:RDF>

This item appears in the following Collection(s)

Search KOPS


Browse

My Account