论文部分内容阅读
健壮性图着色问题(RobustGraphColoringProblem-RGCP)是经典图着色问题的一种新的扩展，它在许多领域有广泛应用。
本论文提出了一个求解小规模数据RGCP的精确解算法。通过改进已有邻域结构，优化了大规模数据RGCP近似解算法。新的基于局部搜索的近似算法，在解质量和时间效率方面都优于已有算法。进一步地，针对区间图的健壮性图着色问题，利用罚分潜在的约束，本文提出若干新的算法。最后，还将健壮性图着色问题算法应用到飞机场调度问题中。