Skip to main content
SpringerLink
Log in

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

  • Published:
Control Theory and Technology Aims and scope Submit manuscript

Abstract

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 is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. N. Barnier, P. Brisset. Graph coloring for air traffic flow management. Annals of Operations Research, 2004, 130(1/4): 163–178.

    Article  MathSciNet  MATH  Google Scholar 

  2. E. Burke, D. Elliman, R. Weare. A university timetabling system based on graph colouring and constraint manipulation. Journal of Research on Computing in Education, 1994, 27(1): 1–18.

    Article  Google Scholar 

  3. M. Carter, G. Laporte, S. Lee. Examination timetabling: algorithmic strategies and applications. Journal of the Operational Resaerch Society, 1996, 47(3): 373–383.

    Article  Google Scholar 

  4. K. Giaro, M. Kubale, P. Obszarski. A graph coloring approach to scheduling of multiprocessor tasks on dedicated machines with availability constraints. Discrete Applied Mathematics, 2009, 157(17): 3625–3630.

    Article  MathSciNet  MATH  Google Scholar 

  5. A. Gamst. Some lower bounds for a class of frequency assignment problems. IEEE Transactions on Vehicular Technology, 1986, 35(1): 8–14.

    Article  Google Scholar 

  6. J. Yáñez, J. Ramírez. The robust coloring problem. European J. of Operational Research, 2003, 148(3): 546–558.

    Article  MathSciNet  MATH  Google Scholar 

  7. F. Wang, Z. Xu. Meta-heuristics for robust graph coloring. Journal of Heuristics, 2013, 19(4): 529–548.

    Article  Google Scholar 

  8. R. Bracho, J. Rodriguez, F. Martinez. Algorithms for robust graph coloring on paths. Proceedings of the 2nd International Conference on Electrical and Electronics Engineering. New York: IEEE, 2005: 9–12.

    Google Scholar 

  9. D. Cheng, H. Qi. Semi-tensor product of matrices theory and applications. Beijing: Science Press, 2007 (in Chinese).

    Google Scholar 

  10. D. Cheng, H. Qi, Z. Li. Analysis and Control of Boolean Networks: A Semi-tensor Product Approach. Berlin: Springer, 2011.

    Book  MATH  Google Scholar 

  11. D. Cheng, H. Qi. A linear representation of dynamics of Boolean networks. IEEE Transactions on Automatic Control, 2010, 55(10): 2251–2258.

    Article  MathSciNet  Google Scholar 

  12. D. Cheng, H. Qi. Controllability and observability of Boolean control networks. Automatica, 2009, 45(7): 1659–1667.

    Article  MathSciNet  MATH  Google Scholar 

  13. D. Cheng, Z. Li, H. Qi. Realization of Boolean control networks. Automatica, 2010, 46(1): 62–69.

    Article  MathSciNet  MATH  Google Scholar 

  14. D. Cheng. Disturbance decoupling of Boolean control networks. IEEE Transactions on Automatic Control, 2011, 56(1): 2–10.

    Article  MathSciNet  Google Scholar 

  15. D. Cheng, H. Qi, Z. Li, et al. Stability and stabilization of Boolean networks. International Journal of Robust and Nonlinear Control, 2011, 21(2): 134–156.

    Article  MathSciNet  MATH  Google Scholar 

  16. D. Cheng, Y. Zhao, X. Xu. From Boolean algebra to Boolean calculus. Control Theory & Applications, 2011, 28(10): 1513–1523.

    MathSciNet  Google Scholar 

  17. H. Qi, D. Cheng. Logic and logic-based control. Journal of Control Theory and Applications, 2008, 6(1): 26–36.

    Article  MathSciNet  MATH  Google Scholar 

  18. Y. Wang, C. Zhang, Z. Liu. A matrix approach to graph maximum stable set and coloring problems with application to multi-agent systems. Automatica, 2012, 48(7): 1227–1236.

    Article  MathSciNet  MATH  Google Scholar 

  19. D. Laschov, M. Margaliot. A maximum principle for singleinput Boolean control networks. IEEE Transactions on Automatic Control, 2011, 56(4): 913–917.

    Article  MathSciNet  Google Scholar 

  20. F. Li, J. Sun. Controllability of higher order Boolean control networks. Applied Mathematics and Computation, 2012, 219(1): 158–169.

    Article  MathSciNet  MATH  Google Scholar 

  21. Z. Li, D. Cheng. Algebraic approach to dynamics of multi-valued networks. International Journal of Bifurcation and Chaos, 2010, 20(3): 561–582.

    Article  MathSciNet  MATH  Google Scholar 

  22. Z. Liu, Y. Wang. General Logical expression of k-valued and mixvalued pseudo-logical functions. Proceedings of the 31st Chinese Control Conference. Piscataway: IEEE, 2012: 66–71.

    Google Scholar 

  23. A. Ge, Y. Wang, A. Wei, et al. Control design for multi-variable fuzzy systems with application to parallel hybrid electric vehicles. Control Theory & Applications, 2013, 30(8): 998–1004.

    Google Scholar 

  24. X. Xu, Y. Hong. Matrix expression and reachability analysis of finite automata. Journal of Control Theory and Applications, 2012, 10(2): 210–215.

    Article  MathSciNet  Google Scholar 

  25. Z. Li, J. Song. Controllability and observability of Boolean control networks. Control Theory & Applications, 2013, 30(6): 760–764.

    Google Scholar 

  26. M. Carter. A survey of practical applications of examination timetabling. Operations Research, 1986, 34(2): 193–202.

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Control Science and Engineering, Shandong University, Jinan Shandong, 250061, China

    Meirong Xu, Yuzhen Wang & Airong Wei

  2. School of Mathematical Sciences, University of Jinan, Jinan Shandong, 250022, China

    Meirong Xu

Authors
  1. Meirong Xu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Yuzhen Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Airong Wei
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Meirong Xu.

Additional information

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), and the Scientific Research and Development Project of Shandong Provincial Education Department (No. J11LA01).

Meirong XU received her B.S. degree from Shandong University in 1996, and M.S. degree from Naval Aeronautical Engineering Institute, China, in 2004. Since 2004, she is an associate professor with the School of Mathematical Sciences, University of Jinan, China. She is currently pursuing the Ph.D. degree in the School of Control Science and Engineering, Shandong University, China. Her interests include graph coloring and semi-tensor product.

Yuzhen WANG graduated from Tai’an Teachers College in 1986, received his M.S. degree from Shandong University of Science & Technology in 1995 and Ph.D. degree from the Institute of Systems Science, Chinese Academy of Sciences in 2001. From 2001 to 2003, he worked as a postdoctoral fellow in Tsinghua University, Beijing, China. Since 2003, he is a professor with the School of Control Science and Engineering, Shandong University, China, and currently the dean of the School of Control Science and Engineering, Shandong University. From March 2004 to June 2004, from February 2006 to May 2006, and from November 2008 to January 2009, he visited City University of Hong Kong as a research fellow. From September 2004 to May 2005, he worked as a visiting research fellow at the National University of Singapore. His research interests include nonlinear control systems, Hamiltonian systems, Boolean networks, and multi-agent systems. Prof. Wang received the Prize of Guan Zhaozhi in 2002, the Prize of Huawei from the Chinese Academy of Sciences in 2001, the Prize of Natural Science from Chinese Education Ministry in 2005, and the National Prize of Natural Science of China in 2008. Currently, he is a Taishan Scholar of Shandong Province, China, an associate editor of Asian Journal of Control, and IMA Journal of Math Control and Inform.

Airong WEI received her M.S. degree from Shandong University of technology in 1997 and Ph.D. degree from School of Control Science and Engineering, Shandong University in 2006. From 2007 to 2009, she worked as a postdoctoral fellow at the School of Mathematics, Shandong University. Currently, she is an associate professor with the School of Control Science and Engineering, Shandong University. Her research interests include nonlinear control systems with constrains, Hamiltonian systems and control of multi-agent systems.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Xu, M., Wang, Y. & Wei, A. Robust graph coloring based on the matrix semi-tensor product with application to examination timetabling. Control Theory Technol. 12, 187–197 (2014). https://doi.org/10.1007/s11768-014-0153-7

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11768-014-0153-7

Keywords

Search

Navigation