Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

Temporal vertex cover with a sliding time window.

Akrida, E.C. and Mertzios, G.B. and Spirakis, P.G. and Zamaraev, V. (2020) 'Temporal vertex cover with a sliding time window.', Journal of computer and system sciences., 107 . pp. 108-123.

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.

Item Type:Article
Full text:(AM) Accepted Manuscript
Available under License - Creative Commons Attribution Non-commercial No Derivatives.
Download PDF
(637Kb)
Status:Peer-reviewed
Publisher Web site:https://doi.org/10.1016/j.jcss.2019.08.002
Publisher statement:© 2019 This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/
Date accepted:09 August 2019
Date deposited:13 August 2019
Date of first online publication:21 August 2019
Date first made open access:21 August 2020

Save or Share this output

Export:
Export
Look up in GoogleScholar