随机图的点可区别V-全染色算法

• 作者: 代素敏 尹波 李敬文 胡腾云
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 图 点可区别V-全染色 点可区别V-全色数
• 年，卷（期）: 2015,（16）
• 所属期刊栏目: 理论研究、研发设计
• 页码范围: 26-29,41
• 页数: 5页
• 分类号: TP301
• 字数: 3529字
• 语种: 中文
• DOI: 10.3778/j.issn.1002-8331.1410-0372

摘要

图G的点可区别V-全染色就是相邻的边、顶点与其关联边必须染不同的颜色，同时要求所有顶点的色集合也不相同，所用的最少颜色数称为图G的点可区别V-全色数。根据点可区别V-全染色的约束规则，设计了一种启发式的点可区别V-全染色算法，该算法借助染色矩阵及色补集合逐步迭代交换，每次迭代交换后判断目标函数值，当目标函数值满足要求时染色成功。给出了算法的详细描述、算法分析和算法测试结果，对给定点数的图进行了点可区别V-全染色猜想的验证。实验结果表明，该算法有很好的执行效率并可以得到给定图的点可区别V-全色数，并且算法的时间复杂度不超过O(n3)。

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李敬文	兰州交通大学电子与信息工程学院	91	810	11.0	26.0
2	胡腾云	兰州交通大学电子与信息工程学院	4	6	2.0	2.0
3	尹波	兰州交通大学电子与信息工程学院	3	6	2.0	2.0
4	代素敏	兰州交通大学电子与信息工程学院	3	6	2.0	2.0