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:

Sliding window temporal graph coloring

Mertzios, G.B. and Molter, H. and Zamaraev, V. (2021) 'Sliding window temporal graph coloring.', Journal of computer and system sciences., 120 . pp. 97-115.

Abstract

Graph coloring is one of the most famous computational problems with applications in a wide range of areas such as planning and scheduling, resource allocation, and pattern matching. So far coloring problems are mostly studied on static graphs, which often stand in contrast to practice where data is inherently dynamic. A temporal graph has an edge set that changes over time. We present a natural temporal extension of the classical graph coloring problem. Given a temporal graph and integers k and Δ, we ask for a coloring sequence with at most k colors for each vertex such that in every time window of Δ consecutive time steps, in which an edge is present, this edge is properly colored at least once. We thoroughly investigate the computational complexity of this temporal coloring problem. More specifically, we prove strong computational hardness results, complemented by efficient exact and approximation algorithms.

Item Type:Article
Full text:(AM) Accepted Manuscript
Available under License - Creative Commons Attribution Non-commercial No Derivatives 4.0.
Download PDF
(476Kb)
Status:Peer-reviewed
Publisher Web site:https://doi.org/10.1016/j.jcss.2021.03.005
Publisher statement:© 2021 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:18 March 2021
Date deposited:16 April 2021
Date of first online publication:07 April 2021
Date first made open access:07 April 2022

Save or Share this output

Export:
Export
Look up in GoogleScholar