Journal of Computer Applications ›› 2017, Vol. 37 ›› Issue (2): 457-462.DOI: 10.11772/j.issn.1001-9081.2017.02.0457

Previous Articles     Next Articles

Adjacent vertex-distinguishing equitable V-total coloring algorithm of graph based on multi-objective optimization

CAO Daotong1, LI Jingwen1, JIANG Hongdou1, WEN Fei2   

  1. 1. School of Electronic and Information Engineering, Lanzhou Jiaotong University, Lanzhou Gansu 730070, China;
    2. Institute of Applied Mathematics, Lanzhou Jiaotong University, Lanzhou Gansu 730070, China
  • Received:2016-06-15 Revised:2016-08-03 Online:2017-02-10 Published:2017-02-11
  • Supported by:
    This work is partially supported by the National Natural Science Foundation of China (11461038, 61163010, 61163037), the Youth Fund of Lanzhou Jiaotong University (2016014).

多目标优化的图的邻点可区别均匀V-全染色算法

曹道通1, 李敬文1, 江红豆1, 文飞2   

  1. 1. 兰州交通大学 电子与信息工程学院, 兰州 730070;
    2. 兰州交通大学 应用数学研究所, 兰州 730070
  • 通讯作者: 曹道通,caodaotong1990@163.com
  • 作者简介:曹道通(1990-),男,江苏徐州人,硕士研究生,主要研究方向:智能计算、组合优化;李敬文(1965-),男,辽宁沈阳人,教授,CCF会员,主要研究方向:图论及应用;江红豆(1991-),女,甘肃庆阳人,硕士研究生,主要研究方向:智能计算、组合优化;文飞(1984-),男,甘肃天水人,讲师,博士,主要研究方向:图论及应用。
  • 基金资助:
    国家自然科学基金资助项目(11461038,61163010,61163037);兰州交通大学青年基金资助项目(2016014)。

Abstract: Adjacent Vertex-Distinguishing Equitable V-Total Coloring (AVDEVTC) of a graph means on the basis of adjacent vertex-distinguishing V-total coloring, the differences between every two colors used in coloring are no more than one. The minimum number of colors used for completing AVDEVTC is called Adjacent Vertex-Distinguishing Equitable V-Total Chromatic Number (AVDEVTCN). A multi-objective optimization coloring algorithm was proposed to resolve the problem of AVDEVTC of the graph. A main objective function and four subobjective functions were designed according to the conditions of AVDEVTC. Every subobjective function was optimized to meet the requirements of the main objective function by the iterative exchange operation of the color set of every vertex on the coloring matrix, thus completed the coloring. Theoretical analysis and experimental comparison show that all of the simple connected graphs within eight vertices have the AVDEVTC, and their AVDEVTCN are between the maximum degree plus 1 and the maximum degree plus 2. The experimental result indicates that the proposed coloring algorithm can correctly calculate the AVDEVTCN of graphs within 1000 vertices in a short period of time.

Key words: coloring algorithm, objective function, multi-objective optimization, Adjacent Vertex-Distinguishing Equitable V-Total Coloring (AVDEVTC), Adjacent Vertex-Distinguishing Equitable V-Total Chromatic Number (AVDEVTCN)

摘要: 图的邻点可区别均匀V-全染色(AVDEVTC)是指在满足邻点可区别V-全染色的基础上,还要保证每种颜色的使用次数相差不超过1,把完成AVDEVTC所用的最少颜色称为图的邻点可区别均匀V-全色数(AVDEVTCN)。针对图的AVDEVTC问题,提出了一种基于多目标优化的染色算法。设计了一个总目标函数和四个子目标函数,在染色矩阵上通过每个点的颜色集合的迭代交换操作,使得每个子目标函数都达到最优,进而满足总目标函数的要求,完成染色。经过理论分析和实验对比表明,8个顶点以内的所有简单连通图都存在AVDEVTC,且图的AVDEVTCN介于最大度加1与最大度加2之间。实验结果表明,该染色算法能够在较短的时间内正确地计算出1000个顶点以内的图的AVDEVTCN。

关键词: 染色算法, 目标函数, 多目标优化, 邻点可区别均匀V-全染色, 邻点可区别均匀V-全色数

CLC Number: