摘要
为解决图的Smarandachely邻点可区别边染色问题,提出一种基于多目标优化的染色算法。针对每个子问题分别设置子目标函数向量和决策空间,在颜色迭代、顺序交换和强制交换中,子目标逐渐得到最优解,最终使总目标函数符合图的Smarandachely邻点可区别边染色要求。实验结果表明,在1 000个顶点内该算法能够正确地得到随机图的Smarandachely邻点可区别边色数。
To solve the problem of Smarandachely Adjacent Vertex Distinguishing Edge Coloring（ SAVDEC） of graphs,t his paper presents a coloring algorithm based on multi-objective optimization. For each sub problem,the sub objective function vector and decision space are set respectively. The optimal solution for sub objectives is gradually obtained during color iteration, sequential switching,and forced switching,making the total objective function meet the requirements of Smarandachely adjacent vertex distinguishing edge coloring ultimately. Experimental results show that,the proposed algorithm is able to get the number of colors for the Smarandachely adjacent vertex distinguishing edge of random graph within 1 000 vertices correctly.
出处
《计算机工程》
CAS
CSCD
北大核心
2017年第9期228-233,239,共7页
Computer Engineering
基金
国家自然科学基金(11461038
61163037
61163010)
兰州交通大学青年基金(2016014)
关键词
多目标优化
图染色
Smarandachely邻点可区别边染色
目标函数
时间复杂度
multi-objective optimization
graph coloring
Smarandachely Adjacent Vertex Distinguishing Edge Coloring（SAVDEC）
objective function
time complexity
