Sliding window temporal graph coloring

Mertzios, George B, Molter, Hendrik and Zamaraev, Viktor ORCID: 0000-0001-5755-4141 (2021) Sliding window temporal graph coloring. Journal of Computer and System Sciences, 120. pp. 97-115.

This is the latest version of this item.

Text
temporal-coloring-jcss-journal.pdf - Author Accepted Manuscript
Download (505kB) | Preview

Official URL: http://dx.doi.org/10.1016/j.jcss.2021.03.005

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
Uncontrolled Keywords:	Time-varying graph, Link stream, NP-hardness, Parameterized complexity, Fixed-parameter tractability, Channel assignment
Divisions:	Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	11 May 2021 09:46
Last Modified:	18 Jan 2023 22:47
DOI:	10.1016/j.jcss.2021.03.005
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3122310