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

• 作者: 李小慧 李敬文 杜永文 董威 贾西贝
• 来源期刊: 计算机应用研究
• 关键词: 随机图 正常全染色 点可区别全染色 算法 邻接矩阵
• 年，卷（期）: 2015,（6）
• 所属期刊栏目: 算法研究探讨
• 页码范围: 1707-1710,1715
• 页数: 5页
• 分类号: TP301.6
• 语种: 中文
• DOI: 10.3969/j.issn.1001-3695.2015.06.023

摘要

点可区别全染色(VDTC)是指在满足正常全染色的基础上,还要使得图中由顶点颜色和其关联边颜色构成的顶点色集合也不同,所使用的最少颜色数称为点可区别全色数.提出了一种针对随机图的点可区别全染色算法,算法的基本思想是对图G中的边随机地进行预染色,查找存在边染色不正常的冲突集,然后根据规则逐步迭代,直至使目标函数的值满足要求,此时说明染色成功.实验结果表明,算法能够有效地求得给定点数随机图的点可区别全色数,算法时间复杂度不超过O(n3).

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李敬文	兰州交通大学电子与信息工程学院	91	810	11.0	26.0
2	杜永文	兰州交通大学电子与信息工程学院	34	85	5.0	6.0
3	贾西贝	兰州交通大学电子与信息工程学院	5	19	3.0	4.0
4	董威	兰州交通大学电子与信息工程学院	4	18	3.0	4.0
5	李小慧	兰州交通大学电子与信息工程学院	4	18	3.0	4.0