作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2012, Vol. 38 ›› Issue (17): 32-34. doi: 10.3969/j.issn.1000-3428.2012.17.009

• 软件技术与数据库 • 上一篇    下一篇

完全图的点可区别强全染色算法

赵焕平1,刘 平1,李敬文2   

  1. (1. 南阳理工学院计算机科学与技术系,河南 南阳 473004;2. 兰州交通大学电子与信息工程学院,兰州 730070)
  • 收稿日期:2011-11-09 修回日期:2011-12-27 出版日期:2012-09-05 发布日期:2012-09-03
  • 作者简介:赵焕平(1981-),女,讲师、硕士,主研方向:图论及其应用;刘 平,讲师、硕士;李敬文,教授

Strong Vertex-distinguishing Total Coloring Algorithm of Complete Graph

ZHAO Huan-ping 1, LIU Ping 1, LI Jing-wen 2   

  1. (1. Department of Computer Science and Technology, Nanyang Institute of Technology, Nanyang 473004, China; 2. School of Electronic and Information Engineering, Lanzhou Jiaotong University, Lanzhou 730070, China)
  • Received:2011-11-09 Revised:2011-12-27 Online:2012-09-05 Published:2012-09-03

摘要: 根据图的点可区别全染色的定义,结合完全图的对称性,提出一种新的点可区别强全染色算法。该算法将需要填充的颜色分为超色数和正常色数2个部分,在得到染色数量和染色次数的前提下,对超色数进行染色以增强算法收敛性。实验结果表明,该算法具有较低的时间复杂度。

关键词: 点可区别强全染色, 点可区别强全色数, 完全图, 超色数, 正常色数

Abstract: According to the definition of strong vertex-distinguishing total coloring, this paper combines with the symmetry of complete graph, proposes a new strong vertex-distinguishing total coloring algorithm. The algorithm divides the filled colors into two parts: overcolor and propercolor. At the premise of getting the coloring number and the coloring frequency, it uses colored at first to enhance its convergence. Experimental results show that this algorithm has a lower time complexity.

Key words: strong vertex-distinguishing total coloring, strong vertex-distinguishing total coloring chromatic number, complete graph, overcolor number, propercolor number

中图分类号: