您的位置：山东大学 -> 科技期刊社 -> 《山东大学学报（工学版）》

山东大学学报(工学版) ›› 2015, Vol. 45 ›› Issue (1): 64-69.doi: 10.6040/j.issn.1672-3961.0.2014.293

• 控制科学与工程 • 上一篇    下一篇

Conflict-free着色问题及其在频率分配中的应用

徐美荣1,2, 王玉振1   

  1. 1. 山东大学控制科学与工程学院, 山东 济南 250061;
    2. 济南大学数学科学学院, 山东 济南 250022
  • 收稿日期:2014-10-16 修回日期:2015-01-13 发布日期:2014-10-16
  • 通讯作者: 王玉振(1963-),男,山东泰安人,教授,博导,博士,主要研究方向为非线性控制,Hamilton控制系统理论,逻辑动态网络,复杂系统.E-mail:yzwang@sdu.edu.cn E-mail:yzwang@sdu.edu.cn
  • 作者简介:徐美荣(1973-),女,江苏徐州人,副教授,博士研究生,主要研究方向为图着色,频率分配.E-mail:ss_xumr@ujn.edu.cn
  • 基金资助:
    国家自然科学基金 (G61374065,G61374002,G61034007); 山东省泰山学者项目基金

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)

646

摘要： 研究了超图的conflict-free着色问题。利用矩阵半张量积方法给出了conflict-free着色的两个充要条件,建立了一个可以确定出所有conflict-free着色方案的新算法。把结果应用于频率分配问题,说明了理论结果的有效性和应用性。

关键词: 半张量积, 代数公式, Conflict-free着色, 超图, 频率分配

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

中图分类号: 

  • 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] 潘金凤,赵建立*,付世华. 逻辑切换控制网络的可控性和稳定性[J]. 山东大学学报(工学版), 2013, 43(4): 62-67.
[2] 葛爱冬1,2,王玉振1*,魏爱荣1. 基于矩阵半张量积方法的随机模糊系统控制器设计[J]. 山东大学学报(工学版), 2013, 43(3): 30-37.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
版权所有 © 2018 《山东大学学报(工学版)》编辑部　
地址: 济南市山大南路27号（250100）　 电话: 0531-88366735　 E-mail: xbgxb@sdu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发