Skip to main content

Research Repository

Advanced Search

Temporal vertex cover with a sliding time window

Akrida, E.C.; Mertzios, G.B.; Spirakis, P.G.; Zamaraev, V.

Temporal vertex cover with a sliding time window Thumbnail


Authors

P.G. Spirakis

V. Zamaraev



Abstract

Modern, inherently dynamic systems are usually characterized by a network structure which is subject to discrete changes over time. Given a static underlying graph, a temporal graph can be represented via an assignment of a set of integer time-labels to every edge, indicating the discrete time steps when this edge is active. While most of the recent theoretical research on temporal graphs focused on temporal paths and other “path-related” temporal notions, only few attempts have been made to investigate “non-path” temporal problems. In this paper we introduce and study two natural temporal extensions of the classical problem VERTEX COVER. We present a thorough investigation of the computational complexity and approximability of these two temporal covering problems. We provide strong hardness results, complemented by approximation and exact algorithms. Some of our algorithms are polynomial-time, while others are asymptotically almost optimal under the Exponential Time Hypothesis (ETH) and other plausible complexity assumptions.

Citation

Akrida, E., Mertzios, G., Spirakis, P., & Zamaraev, V. (2020). Temporal vertex cover with a sliding time window. Journal of Computer and System Sciences, 107, 108-123. https://doi.org/10.1016/j.jcss.2019.08.002

Journal Article Type Article
Acceptance Date Aug 9, 2019
Online Publication Date Aug 21, 2019
Publication Date Feb 28, 2020
Deposit Date Aug 11, 2019
Publicly Available Date Aug 21, 2020
Journal Journal of Computer and System Sciences
Print ISSN 0022-0000
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 107
Pages 108-123
DOI https://doi.org/10.1016/j.jcss.2019.08.002
Related Public URLs https://arxiv.org/abs/1802.07103

Files





You might also like



Downloadable Citations