## 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 language | English |
---|---|

Pages (from-to) | 81-91 |

Number of pages | 11 |

Journal | Proceedings of the Workshop on Algorithm Engineering and Experiments |

DOIs | |

Publication status | Published - 2 Jan 2019 |

Event | 21st Workshop on Algorithm Engineering and Experiments, ALENEX 2019 - San Diego, United States Duration: 7 Jan 2019 → 8 Jan 2019 |

## Scopus Subject Areas

- Engineering(all)
- Applied Mathematics