Skip to main content

Research Repository

Advanced Search

Sliding window temporal graph coloring

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

Sliding window temporal graph coloring Thumbnail


Authors

H. Molter

V. Zamaraev



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
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 120
Pages 97-115
DOI https://doi.org/10.1016/j.jcss.2021.03.005

Files





You might also like



Downloadable Citations