Network evolution driven by dynamics applied to graph coloring  

作　　者：吴建设 李力光 王晓华 于昕 焦李成 

机构地区：[1]Key Laboratory of Intelligent Perception and Image Understanding of Ministry of Education of China,224# Xidian University [2]Aeronautical Computing Technique Research Institute

出　　处：《Chinese Physics B》2013年第6期262-267,共6页中国物理B（英文版）

基　　金：supported by the National Natural Science Foundation of China (Grants Nos. 61072139,61072106,61203303,61003198,61272279,and 61003199)

摘　　要：An evolutionary network driven by dynamics is studied and applied to the graph coloring problem. From an initial structure, both the topology and the coupling weights evolve according to the dynamics. On the other hand, the dynamics of the network are determined by the topology and the coupling weights, so an interesting structure-dynamics co-evolutionary scheme appears. By providing two evolutionary strategies, a network described by the complement of a graph will evolve into several clusters of nodes according to their dynamics. The nodes in each cluster can be assigned the same color and nodes in different clusters assigned different colors. In this way, a co-evolution phenomenon is applied to the graph coloring problem. The proposed scheme is tested on several benchmark graphs for graph coloring.An evolutionary network driven by dynamics is studied and applied to the graph coloring problem. From an initial structure, both the topology and the coupling weights evolve according to the dynamics. On the other hand, the dynamics of the network are determined by the topology and the coupling weights, so an interesting structure-dynamics co-evolutionary scheme appears. By providing two evolutionary strategies, a network described by the complement of a graph will evolve into several clusters of nodes according to their dynamics. The nodes in each cluster can be assigned the same color and nodes in different clusters assigned different colors. In this way, a co-evolution phenomenon is applied to the graph coloring problem. The proposed scheme is tested on several benchmark graphs for graph coloring.

关 键 词：network dynamics evolution of network evolutionary strategies graph coloring problem 

分 类 号：O157.5[理学—数学]