| 随机图的邻点可区别V-全染色算法 |
| |
| 引用本文： | 贾西贝,、董威,、李小慧,、李敬文.随机图的邻点可区别V-全染色算法[J].西南师范大学学报(自然科学版),2015,40(2):14-19. |
| |
| 作者姓名： | 贾西贝 、董威 、李小慧 、李敬文 |
| |
| 作者单位： | 兰州交通大学电子与信息工程学院 |
| |
| 基金项目： | 国家自然科学基金项目(11461038;61163010;61163037) |
| |
| 摘 要： | 图G的邻点可区别V-全染色就是相邻的边、顶点与其关联边必须染不同的颜色,同时要求相邻顶点的色集合也不相同,所用的最少颜色数称为图G的邻点可区别V-全色数.根据邻点可区别V-全染色的约束规则,设计了一种启发式的邻点可区别V-全染色算法.该算法借助染色矩阵及色补集合逐步迭代交换,每次迭代交换后判断目标函数值,当目标函数值满足要求时染色成功.给出了算法的详细描述以及算法分析和算法测试结果.实验结果表明,该算法有很好的执行效率,并可以得到随机图的邻点可区别V-全色数,验证了邻点可区别V-全染色猜想,并且算法的时间复杂度不超过O(n3).
|
| 关 键 词： | 随机图 算法 邻点可区别V-全染色 邻点可区别V-全色数 |
On Algorithm for Adjacent Vertex Distinguishing V-Total Coloring of Random Graphs |
| |
| JIA Xi-bei,DONG Wei,LI Xiao-hui,LI Jing-wen.On Algorithm for Adjacent Vertex Distinguishing V-Total Coloring of Random Graphs[J].Journal of Southwest China Normal University(Natural Science),2015,40(2):14-19. |
| |
| Authors: | JIA Xi-bei DONG Wei LI Xiao-hui LI Jing-wen |
| |
| Institution: | JIA Xi-bei;DONG Wei;LI Xiao-hui;LI Jing-wen;School of Electronic and Information Engineering,Lanzhou Jiaotong University; |
| |
| Abstract: | |
| |
| Keywords: | |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《西南师范大学学报(自然科学版)》浏览原始摘要信息 |
| 点击此处可从《西南师范大学学报(自然科学版)》下载免费的PDF全文 |
|
