Robust graph coloring based on the matrix semi-tensor product with application to examination timetabling
Meirong XU
Yuzhen WANG
Airong WEI
摘要：This paper investigates the robust graph coloring problem with application to a kind of examination timetabling by using the matrix semi-tensor product, and presents a number of new results and algorithms. First, using the matrix semi-tensor product, the robust graph coloring is expressed into a kind of optimization problem taking in an algebraic form of matrices, based on which an algorithm is designed to find all the most robust coloring schemes for any simple graph. Second, an equivalent problem of robust graph coloring is studied, and a necessary and sufficient condition is proposed, from which a new algorithm to find all the most robust coloring schemes is established. Third, a kind of examination timetabling is discussed by using the obtained results, and a method to design a practicable timetabling scheme is presented. Finally, the effectiveness of the results/algorithms presented in this paper is shown by two illustrative examples.
机标关键词：graph coloringsufficient conditionoptimization problemcoloring problemnew algorithmsimple graphform of
资助基金：the National Natural Science Foundation of China()the National Natural Science Foundation of China( G61374065)the National Natural Science Foundation of China( G61034007)the National Natural Science Foundation of China( G61374002)the Fund for the Taishan Scholar Project of Shandong Province, the Natural Science Foundation of Shandong Province(ZR2010FM013)the Scientific Research and Development Project of Shandong Provincial Education Department(J11LA01)
论文发表日期：2014-01-01
在线出版日期：2025-08-15（本平台首次上网日期，不代表文献的发表时间）
页数：11( 187-197 )
英文信息