| 随机图的点可区别全染色算法 |
| |
| 引用本文： | 李敬文,李小慧,董威,贾西贝,杜永文.随机图的点可区别全染色算法[J].计算机应用研究,2015,32(6). |
| |
| 作者姓名： | 李敬文 李小慧 董威 贾西贝 杜永文 |
| |
| 作者单位： | 兰州交通大学电子与信息工程学院,兰州,730070 |
| |
| 基金项目： | 国家自然科学基金资助项目 |
| |
| 摘 要： | 点可区别全染色(VDTC)是指在满足正常全染色的基础上,还要使得图中由顶点颜色和其关联边颜色构成的顶点色集合也不同,所使用的最少颜色数称为点可区别全色数.提出了一种针对随机图的点可区别全染色算法,算法的基本思想是对图G中的边随机地进行预染色,查找存在边染色不正常的冲突集,然后根据规则逐步迭代,直至使目标函数的值满足要求,此时说明染色成功.实验结果表明,算法能够有效地求得给定点数随机图的点可区别全色数,算法时间复杂度不超过O(n3).
|
| 关 键 词： | 随机图 正常全染色 点可区别全染色 算法 邻接矩阵 |
Algorithm for vertex distinguishing total coloring of random graphs |
| |
| Li Jingwen,Li Xiaohui,Dong Wei,Jia Xibei,Du Yongwen.Algorithm for vertex distinguishing total coloring of random graphs[J].Application Research of Computers,2015,32(6). |
| |
| Authors: | Li Jingwen Li Xiaohui Dong Wei Jia Xibei Du Yongwen |
| |
| Abstract: | |
| |
| Keywords: | random graphs proper-total-coloring vertex-distinguish-coloring algorithm adjacency matrix |
| 本文献已被 万方数据 等数据库收录！ |
|
