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.
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.
|Full text:||(AM) Accepted Manuscript|
Available under License - Creative Commons Attribution Non-commercial No Derivatives 4.0.
Download PDF (476Kb)
|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
|Look up in GoogleScholar|