Robust graph coloring based on the matrix semi-tensor product with application to examination timetabling  

作　　者：Meirong XU Yuzhen WANG Airong WEI 

机构地区：[1]School of Control Science and Engineering, Shandong University, Jinan Shandong 250061, China [2]School of Mathematical Sciences, University of Jinan, Jinan Shandong 250022, China

出　　处：《Control Theory and Technology》2014年第2期187-197,共11页控制理论与技术（英文版）

基　　金：This work was supported by the National Natural Science Foundation of China （Nos. G61374065, G61034007, G61374002）; the Fund for the Taishan Scholar Project of Shandong Province, the Natural Science Foundation of Shandong Province （No. ZR2010FM013）; the Scientific Research and Development Project of Shandong Provincial Education Department （No. J11LA01 ）

摘　　要：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.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.

关 键 词：Robust graph coloring ALGORITHM Examination timetabling Semi-tensor product 

分 类 号：O157.5[理学—数学] TP317[理学—基础数学]