Concatenated k-path covers

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

doi:10.1137/1.9781611975499.7

Concatenated k-path covers

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

Department of Computer Science

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

3 Citations (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 language	English
Title of host publication	2019 Proceedings of the Twenty-First Workshop on Algorithm Engineering and Experiments (ALENEX)
Editors	Stephen Kobourov, Henning Meyerhenke
Publisher	Society for Industrial and Applied Mathematics (SIAM)
Pages	81-91
Number of pages	11
DOIs	https://doi.org/10.1137/1.9781611975499.7
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 https://epubs.siam.org/doi/book/10.1137/1.9781611975499

Publication series

Name	Proceedings of the Workshop on Algorithm Engineering and Experiments
ISSN (Print)	2164-0300

Conference

Conference	21st Workshop on Algorithm Engineering and Experiments, ALENEX 2019
Country/Territory	United States
City	San Diego
Period	7/01/19 → 8/01/19
Internet address	https://epubs.siam.org/doi/book/10.1137/1.9781611975499

Scopus Subject Areas

Engineering(all)
Applied Mathematics

Access to Document

10.1137/1.9781611975499.7

Cite this

Beck, M., Lam, K. Y., NG, J. K. Y., Storandt, S., & Zhu, C. J. (2019). Concatenated k-path covers. In S. Kobourov, & H. Meyerhenke (Eds.), 2019 Proceedings of the Twenty-First Workshop on Algorithm Engineering and Experiments (ALENEX) (pp. 81-91). (Proceedings of the Workshop on Algorithm Engineering and Experiments). Society for Industrial and Applied Mathematics (SIAM). https://doi.org/10.1137/1.9781611975499.7

@inproceedings{ced3020f34ab45f4890ed27123e26257,

title = "Concatenated k-path covers",

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.",

author = "Moritz Beck and Lam, {Kam Yiu} and NG, {Joseph K Y} and Sabine Storandt and Zhu, {Chun Jiang}",

note = "Funding Information: We acknowledge the support of the DFG under grant STO 1114/4-1.; 21st Workshop on Algorithm Engineering and Experiments, ALENEX 2019 ; Conference date: 07-01-2019 Through 08-01-2019",

year = "2019",

month = jan,

day = "2",

doi = "10.1137/1.9781611975499.7",

language = "English",

series = "Proceedings of the Workshop on Algorithm Engineering and Experiments",

publisher = "Society for Industrial and Applied Mathematics (SIAM)",

pages = "81--91",

editor = "Stephen Kobourov and Henning Meyerhenke",

booktitle = "2019 Proceedings of the Twenty-First Workshop on Algorithm Engineering and Experiments (ALENEX)",

address = "United States",

url = "https://epubs.siam.org/doi/book/10.1137/1.9781611975499",

}

Beck, M, Lam, KY, NG, JKY, Storandt, S & Zhu, CJ 2019, Concatenated k-path covers. in S Kobourov & H Meyerhenke (eds), 2019 Proceedings of the Twenty-First Workshop on Algorithm Engineering and Experiments (ALENEX). Proceedings of the Workshop on Algorithm Engineering and Experiments, Society for Industrial and Applied Mathematics (SIAM), pp. 81-91, 21st Workshop on Algorithm Engineering and Experiments, ALENEX 2019, San Diego, United States, 7/01/19. https://doi.org/10.1137/1.9781611975499.7

Concatenated k-path covers. / Beck, Moritz; Lam, Kam Yiu; NG, Joseph K Y et al.
2019 Proceedings of the Twenty-First Workshop on Algorithm Engineering and Experiments (ALENEX). ed. / Stephen Kobourov; Henning Meyerhenke. Society for Industrial and Applied Mathematics (SIAM), 2019. p. 81-91 (Proceedings of the Workshop on Algorithm Engineering and Experiments).

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

TY - GEN

T1 - Concatenated k-path covers

AU - Beck, Moritz

AU - Lam, Kam Yiu

AU - NG, Joseph K Y

AU - Storandt, Sabine

AU - Zhu, Chun Jiang

N1 - Funding Information: We acknowledge the support of the DFG under grant STO 1114/4-1.

PY - 2019/1/2

Y1 - 2019/1/2

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85065192706&partnerID=8YFLogxK

U2 - 10.1137/1.9781611975499.7

DO - 10.1137/1.9781611975499.7

M3 - Conference proceeding

AN - SCOPUS:85065192706

T3 - Proceedings of the Workshop on Algorithm Engineering and Experiments

SP - 81

EP - 91

BT - 2019 Proceedings of the Twenty-First Workshop on Algorithm Engineering and Experiments (ALENEX)

A2 - Kobourov, Stephen

A2 - Meyerhenke, Henning

PB - Society for Industrial and Applied Mathematics (SIAM)

T2 - 21st Workshop on Algorithm Engineering and Experiments, ALENEX 2019

Y2 - 7 January 2019 through 8 January 2019

ER -

Beck M, Lam KY, NG JKY, Storandt S, Zhu CJ. Concatenated k-path covers. In Kobourov S, Meyerhenke H, editors, 2019 Proceedings of the Twenty-First Workshop on Algorithm Engineering and Experiments (ALENEX). Society for Industrial and Applied Mathematics (SIAM). 2019. p. 81-91. (Proceedings of the Workshop on Algorithm Engineering and Experiments). doi: 10.1137/1.9781611975499.7

Concatenated k-path covers

Abstract

Publication series

Conference

Scopus Subject Areas

Access to Document

Other files and links

Cite this