Tackling the edge dynamic graph colouring problem with and without future adjacency information
本文针对约束随时间变化的边动态图着色问题，提出了几种启发式方法，在时间步之间调整可行着色，并比较了随机变化和已知未来变化概率两种情况下的效果。
Many real world operational research problems, such as frequency assignment and exam timetabling, can be reformulated as graph colouring problems (GCPs). Most algorithms for the GCP operate under the assumption that its constraints are fixed, allowing us to model the problem using a static graph. However, in many real-world cases this does not hold and it is more appropriate to model problems with constraints that change over time using an edge dynamic graph. Although exploring methods for colouring dynamic graphs has been identified as an area of interest with many real-world applications, to date, very little literature exists regarding such methods. In this paper we present several heuristic methods for modifying a feasible colouring at time-step t into an initial, but not necessarily feasible, colouring for a “similar” graph at time-step $$t+1$$ . We will discuss two cases; (1) where changes occur at random, and (2) where probabilistic information about future changes is provided. Experimental results are also presented and the benefits of applying these particular modification methods are investigated.