### Conflict-free coloring problem with appliction to frequency assignment

XU Meirong1,2, WANG Yuzhen1

1. 1. School of Control Science and Engineering, Shandong University, Jinan 250061, China;
2. School of Mathematical Sciences, University of Jinan, Jinan 250022, China
• Received:2014-10-16 Revised:2015-01-13 Published:2014-10-16

Abstract: The conflict-free coloring problem of hypergraphs was investigated, and some new results and algorithms were obtained. Using the semi-tensor product method, two necessary and sufficient conditions were proposed for the conflict-free coloring problem based on which a new algorithm was established to find all the conflict-free coloring schemes for any hypergraph. Then the theoretical results were applied to the frequency assignment problem to show its effectiveness and applicability.

CLC Number:

• TN915
 [1] EVEN G, LOTKER Z, RON D, et al. Conflict-free colorings of simple geometric regions with application to frequency assignment in cellular networks [J]. SIAM Journal on Scientific Computing, 2003, 33:94-136.[2] CHEILARIS P, TÓTH G. Graph unique-maximum and conflict-free colorings [C]//Proceedings of 7th International Conference on Algorithms and Complexity (CIAC), Rome, Italy:Springer, 2010:143-154.[3] CHEN K, FIAT A, LEVY M, et al. Online conflict-free coloring for intervals [J]. SIAM Journal on Scientific Computing, 2006(36):545-554.[4] HAR-PELED S, SMORODINSKY S. Conflict-free coloring of points and simple regions in the plane[J]. Discrete and Computational Geometry, 2005(34):47-70.[5] CHEILARIS P, TÓTH G. Graph unique-maximum and conflict-free colorings[J]. Journal of Discrete Algorithms, 2011, 9:241-251.[6] 程代展,齐洪胜. 矩阵的半张量积理论与应用[M]. 北京:科学出版社,2007:10-15. CHENG Daizhan, QI Hongsheng. Semi-tensor Product of Matrices: Theory and Applications [M]. Beijing: Science Press, 2007:10-15.[7] CHENG D Z, QI H S, LI Z Q. Analysis and control of Boolean networks: A semi-tensor product approach [M]. London: Springer, 2011:25.[8] CHENG D Z, QI H S. Controllability and observability of Boolean control networks [J]. Automatica, 2009,45(7):1659-1667.[9] CHENG D Z. Disturbance decoupling of Boolean control networks [J]. IEEE Transactions on Automatic Control, 2011, 56(1):2-10.[10] CHENG D Z, LI Z Q, QI H S. Realization of Boolean control networks [J]. Automatica, 2010, 46(1):62-69.[11] 程代展,赵寅,徐相如. 混合值逻辑及其应用[J]. 山东大学学报:理学版, 2011, 46(10):32-44. CHENG Daizhan, ZHAO Yin, XU Xiangru. Mix-valued logic and its applications[J] Journal of Shandong University: Natural Science, 2011, 46(10):32-44.[12] LI F F, SUN J T. Controllability of Boolean control networks with time delays in states[J]. Automatica, 2011, 47(3):603-607.[13] LI F F, SUN J T. Controllability of probabilistic Boolean control networks[J]. Automatica, 2011, 47(12):2765-2771.[14] LI F F, SUN J T, WU Q. Observability of Boolean control networks with state time delays[J]. IEEE Transaction on Neural Networks, 2011, 22(6):948-954.[15] FOMASINI E, VALCHER M. Observability, reconstructibility and state observers of Boolean control networks[J]. IEEE Transactions on Automatic Control, 2013, 58(6):1390-1401.[16] XU X R, HONG Y G. Solvability and control design for synchronization of Boolean networks[J]. Journal of Systems Science and Complexity, 2013, 26(6):871-885.[17] LI R, YANG M, CHU T G. State feedback stabilization for Boolean control networks[J]. IEEE Transactions on Automatic Control, 2013, 58(7):1853-1857.[18] YANG M, LI R, CHU T G. Controller design for disturbance decoupling of Boolean control networks[J]. Automatica, 2013, 49(1):273-277.[19] LI H T, WANG Y Z. Output feedback stabilization control design for Boolean control networks[J]. Automatica, 2013, 49(12):3641-3645.[20] LIU Z B, WANG Y Z. Disturbance decoupling of mix-valued logical networks via the semi-tensor product method[J]. Automatica, 2012, 48(8):1839-1844.[21] 段培永,吕红丽,冯俊娥,等.室内热舒适环境的模糊关系矩阵模型控制系统[J].控制理论与应用,2013, 30(2):215-221. DUAN Peiyong, L Hongli, FENG Jun-e, et al. Fuzzy relation matrix model control system for indoor thermal comfort[J] Control Theory & Application, 2013, 30(2):215-221.[22] CHENG D Z, FENG J, LV H L. Solving fuzzy relational equations via semi-tensor product[J]. IEEE Transaction on Fuzzy Systems, 2012, 20(2):390-396.[23] WANG Y Z, ZHANG C H, LIU Z B. A matrix approach to graph maximum stable set and coloring problems with application to multiagent systems[J]. Automatica, 2012, 48(7):1227-1236.[24] XU M R, WANG Y Z, WEI A R. Robust graph coloring based on matrix semi-tensor product with application to examination timetabling [J]. Control Theory and Technology, 2014, 12(2):187-197.[25] MENG M, FENG J E. A matrix approach to hypergraph stable set and coloring problems with its application to storing problem [J]. Journal of Applied Mathematics, 2014, Article ID: 783784, 9 pages.[26] CHENG D Z, HE F, XU T. On networked non-cooperative games-Asemitensor product approach[C]//Proceedings of the 9th Asian Control Conference, Istanbul:ACC, 2013:1-6.[27] GUO P L, WANG Y Z, LI H T. Algebraic formulation and strategy optimization for a class of evolutionary network games via semi-tensor product method[J]. Automatica, 2013, 49(11):3384-3389.[28] XU X R, HONG Y G. Matrix expression and reachability analysis of finite automata[J]. Journal of Control Theory and Application, 2012, 10:210-215.[29] XU X R, HONG Y G. Matrix approach to model matching of asynchronous sequential machines [J]. IEEE Transactions on Automatic Control, 2013, 58(11):2974-2979.[30] BERGE C. Graphs and hypergraphs[M]. North-Holand:Amsterdam, 1973:37-39.
 [1] PAN Jin-feng, ZHAO Jian-li*, FU Shi-hua. On controllability and stability of switched logical control networks [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2013, 43(4): 62-67. [2] GE Ai-dong1, 2, WANG Yu-zhen1*, WEI Ai-rong1. Controller design of stochastic fuzzy systems based on the semi-tensor product method of matrices [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2013, 43(3): 30-37.
Viewed
Full text

Abstract

Cited

Shared
Discussed