图的邻点可区别全染色算法

• 作者: 李小慧 李敬文 董威 贾西贝 闫光辉
• 来源期刊: 山东大学学报（理学版）
• 学科: 工学
• 关键词: 图 算法 邻点可区别全染色 邻点可区别全色数
• 年，卷（期）: 2015,（2）
• 页码范围: 14-21
• 页数: 8页
• 分类号: TP301
• 字数: 4253字
• 语种: 中文
• DOI: 10.6040/j.issn.1671-9352.0.2014.145

摘要

在图 G 的一个正常全染色下，G 中任意一点 v 的色集合是指点 v 的色以及与 v 关联的全体边的色所构成的集合。图 G 的邻点可区别全染色就是图 G 的正常全染色且使相邻点的色集合不同，其所用最少颜色数称为图 G的邻点可区别全色数。设计了一种启发式的邻点可区别全染色算法，该算法根据邻点可区别全染色的约束规则，确定四个子目标函数和一个总目标函数，然后借助染色矩阵及色补集合逐步迭代交换，每次迭代交换后判断目标函数值，当目标函数值满足要求时染色成功。实验结果表明，该算法可以得到图的邻点可区别全色数，并且算法的时间复杂度不超过 O（n3）。

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李敬文	兰州交通大学电子与信息工程学院	91	810	11.0	26.0
2	闫光辉	兰州交通大学电子与信息工程学院	37	170	8.0	12.0
3	贾西贝	兰州交通大学电子与信息工程学院	5	19	3.0	4.0
4	董威	兰州交通大学电子与信息工程学院	4	18	3.0	4.0
5	李小慧	兰州交通大学电子与信息工程学院	4	18	3.0	4.0