Publikation:

Concatenated k-Path Covers

Vorschaubild

Dateien

Zu diesem Dokument gibt es keine Dateien.

Datum

2019

Autor:innen

Lam, Kam-Yiu
Ng, Joseph Kee Yin
Zhu, Chun Jiang

Herausgeber:innen

Kontakt

ISSN der Zeitschrift

Electronic ISSN

ISBN

Bibliografische Daten

Verlag

Schriftenreihe

Auflagebezeichnung

URI (zitierfähiger Link)
DOI (zitierfähiger Link)
https://doi.org/10.1137/1.9781611975499.7
ArXiv-ID

Internationale Patentnummer

Angaben zur Forschungsförderung

Projekt

Open Access-Veröffentlichung

Sammlungen

Informatik und Informationswissenschaft: Publikationen
Core Facility der Universität Konstanz

Gesperrt bis

Titel in einer weiteren Sprache

Publikationstyp
Beitrag zu einem Konferenzband
Publikationsstatus
Published

Erschienen in

KOBOUROV, Stephen, ed., Henning MEYERHENKE, ed.. 2019 Proceedings of the Twenty-First Workshop on Algorithm Engineering and Experiments (ALENEX). Philadelphia, PA: SIAM, 2019, pp. 81-91. ISBN 978-1-61197-549-9. Available under: doi: 10.1137/1.9781611975499.7

Zusammenfassung

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.

Zusammenfassung in einer weiteren Sprache

Fachgebiet (DDC)
004 Informatik

Schlagwörter

Konferenz

The Twenty-First Workshop on Algorithm Engineering and Experiments (ALENEX), 7. Jan. 2019 - 8. Jan. 2019, San Diego, California
Rezension
undefined / . - undefined, undefined

Forschungsvorhaben

Organisationseinheiten

Zeitschriftenheft

Zugehörige Datensätze in KOPS

Zitieren

ISO 690BECK, 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, 7. Jan. 2019 - 8. Jan. 2019. In: KOBOUROV, Stephen, ed., Henning MEYERHENKE, ed.. 2019 Proceedings of the Twenty-First Workshop on Algorithm Engineering and Experiments (ALENEX). Philadelphia, PA: SIAM, 2019, pp. 81-91. ISBN 978-1-61197-549-9. Available under: doi: 10.1137/1.9781611975499.7
BibTex
@inproceedings{Beck2019-01-02Conca-44521,
  year={2019},
  doi={10.1137/1.9781611975499.7},
  title={Concatenated k-Path Covers},
  isbn={978-1-61197-549-9},
  publisher={SIAM},
  address={Philadelphia, PA},
  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: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/44521">
    <dc:contributor>Lam, Kam-Yiu</dc:contributor>
    <dc:creator>Storandt, Sabine</dc:creator>
    <dc:creator>Beck, Moritz</dc:creator>
    <dc:creator>Lam, Kam-Yiu</dc:creator>
    <dc:language>eng</dc:language>
    <dcterms:issued>2019-01-02</dcterms:issued>
    <dc:contributor>Ng, Joseph Kee Yin</dc:contributor>
    <dc:contributor>Storandt, Sabine</dc:contributor>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2019-01-10T15:18:05Z</dcterms:available>
    <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/44521"/>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2019-01-10T15:18:05Z</dc:date>
    <dc:creator>Ng, Joseph Kee Yin</dc:creator>
    <dc:creator>Zhu, Chun Jiang</dc:creator>
    <dc:contributor>Zhu, Chun Jiang</dc:contributor>
    <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>
    <dcterms:title>Concatenated k-Path Covers</dcterms:title>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:contributor>Beck, Moritz</dc:contributor>
  </rdf:Description>
</rdf:RDF>

Interner Vermerk

xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter

Kontakt
URL der Originalveröffentl.

Prüfdatum der URL

Prüfungsdatum der Dissertation

Finanzierungsart

Kommentar zur Publikation

Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Ja
Begutachtet
Diese Publikation teilen