Concatenated k-path covers

Moritz Beck, Kam Yiu Lam, Joseph K Y NG, Sabine Storandt, Chun Jiang Zhu

Research output: Contribution to journalConference articlepeer-review

1 Citation (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)81-91
Number of pages11
JournalProceedings of the Workshop on Algorithm Engineering and Experiments
VolumeJanuary
DOIs
Publication statusPublished - 2019
Event21st Workshop on Algorithm Engineering and Experiments, ALENEX 2019 - San Diego, United States
Duration: 7 Jan 20198 Jan 2019

Scopus Subject Areas

  • Engineering(all)
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Concatenated k-path covers'. Together they form a unique fingerprint.

Cite this