JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE) ›› 2015, Vol. 45 ›› Issue (1): 64-69.doi: 10.6040/j.issn.1672-3961.0.2014.293

Previous Articles     Next Articles

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

PDF (PC)

609

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.

Key words: semi-tensor product, algebraic formula, conflict-free coloring, hypergraph, frequency assignment

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   
No Suggested Reading articles found!
Copyright 2018 © Editorial office of Journal of Shandong University (Engineering Science)
Supported by Beijing Magtech Co.Ltd