Sliding window temporal graph coloring

Mertzios, G.B.; Molter, H.; Zamaraev, V.

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.

Citation

Mertzios, G., Molter, H., & Zamaraev, V. (2021). Sliding window temporal graph coloring. Journal of Computer and System Sciences, 120, 97-115. https://doi.org/10.1016/j.jcss.2021.03.005

• Journal Article Type: Article
• Acceptance Date: Mar 18, 2021
• Online Publication Date: Apr 7, 2021
• Publication Date: 2021-09
• Deposit Date: Apr 15, 2021
• Publicly Available Date: Apr 7, 2022
• Journal: Journal of Computer and System Sciences
• Print ISSN: 0022-0000
• Electronic ISSN: 1090-2724
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 120
• Pages: 97-115
• DOI: https://doi.org/10.1016/j.jcss.2021.03.005
• Public URL: https://durham-repository.worktribe.com/output/1249799