Publikation:

Concatenated k-path covers

Lade...
Vorschaubild

Dateien

Zu diesem Dokument gibt es keine Dateien.

Datum

2023

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)
ArXiv-ID

Internationale Patentnummer

Angaben zur Forschungsförderung

Projekt

Open Access-Veröffentlichung
Core Facility der Universität Konstanz

Gesperrt bis

Titel in einer weiteren Sprache

Publikationstyp
Zeitschriftenartikel
Publikationsstatus
Published

Erschienen in

International Journal of Computer Mathematics: Computer Systems Theory. Taylor & Francis. 2023, 8(1), S. 32-56. ISSN 2379-9927. eISSN 2379-9935. Verfügbar unter: doi: 10.1080/23799927.2023.2173656

Zusammenfassung

Given a graph G(V,E), a k-Path Cover is defined as a subset C of the nodes V such that every simple path in G consisting of k nodes contains at least one node from C. Similarly, a k-Shortest Path Cover has to contain at least one node of every shortest path in G that consists of k nodes. In this paper, we extend the notion of k-(Shortest) 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 p|k-Shortest Path Covers, we present theoretical results regarding the VC-dimension of the concatenated path set in dependency of p in undirected as well as directed graphs. By proving a low VC-dimension in both settings, we enable the design of efficient approximation algorithms. Furthermore, we discuss how a pruning algorithm originally developed for k-Path Cover computation can be abstracted and modified in order to also solve concatenated p|k-Path Cover problems. A crucial ingredient for the pruning algorithm to work efficiently is a path concatenation recognition algorithm. We describe general recognition algorithms for simple path concatenations as well as shortest path concatenations. Subsequently, we present more refined results for interesting special cases as piecewise shortest paths, hyperpaths, round tours, and trees. 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

Shortest paths, hitting set, vc-dimension

Konferenz

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, 2023. Concatenated k-path covers. In: International Journal of Computer Mathematics: Computer Systems Theory. Taylor & Francis. 2023, 8(1), S. 32-56. ISSN 2379-9927. eISSN 2379-9935. Verfügbar unter: doi: 10.1080/23799927.2023.2173656
BibTex
@article{Beck2023-01-02Conca-70741,
  year={2023},
  doi={10.1080/23799927.2023.2173656},
  title={Concatenated <i>k</i>-path covers},
  number={1},
  volume={8},
  issn={2379-9927},
  journal={International Journal of Computer Mathematics: Computer Systems Theory},
  pages={32--56},
  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/70741">
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dc:contributor>Zhu, Chun Jiang</dc:contributor>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/70741"/>
    <dcterms:abstract>Given a graph G(V,E), a k-Path Cover is defined as a subset C of the nodes V such that every simple path in G consisting of k nodes contains at least one node from C. Similarly, a k-Shortest Path Cover has to contain at least one node of every shortest path in G that consists of k nodes. In this paper, we extend the notion of k-(Shortest) 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 p|k-Shortest Path Covers, we present theoretical results regarding the VC-dimension of the concatenated path set in dependency of p in undirected as well as directed graphs. By proving a low VC-dimension in both settings, we enable the design of efficient approximation algorithms. Furthermore, we discuss how a pruning algorithm originally developed for k-Path Cover computation can be abstracted and modified in order to also solve concatenated p|k-Path Cover problems. A crucial ingredient for the pruning algorithm to work efficiently is a path concatenation recognition algorithm. We describe general recognition algorithms for simple path concatenations as well as shortest path concatenations. Subsequently, we present more refined results for interesting special cases as piecewise shortest paths, hyperpaths, round tours, and trees. An extensive experimental study on different graph types proves the applicability and efficiency of our approaches.</dcterms:abstract>
    <dc:contributor>Lam, Kam-Yiu</dc:contributor>
    <dc:contributor>Ng, Joseph Kee Yin</dc:contributor>
    <dc:language>eng</dc:language>
    <dc:contributor>Storandt, Sabine</dc:contributor>
    <dc:creator>Ng, Joseph Kee Yin</dc:creator>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:creator>Lam, Kam-Yiu</dc:creator>
    <dc:contributor>Beck, Moritz</dc:contributor>
    <dcterms:issued>2023-01-02</dcterms:issued>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2024-09-06T06:39:11Z</dc:date>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2024-09-06T06:39:11Z</dcterms:available>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:creator>Storandt, Sabine</dc:creator>
    <dcterms:title>Concatenated &lt;i&gt;k&lt;/i&gt;-path covers</dcterms:title>
    <dc:creator>Beck, Moritz</dc:creator>
    <dc:creator>Zhu, Chun Jiang</dc:creator>
  </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
Unbekannt
Diese Publikation teilen