Network evolution driven by dynamics applied to 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 weig...

Full description

Saved in:
Bibliographic Details
Published in:Chinese physics B 2013-06, Vol.22 (6), p.262-267, Article 060507
Main Author: 吴建设 李力光 王晓华 于昕 焦李成
Format: Article
Language:English
Subjects:
Clusters
Color
Dynamics
Evolution
Evolutionary
Graph coloring
Graphs
Joining
Networks
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1674-1056
2058-3834
1741-4199
DOI:10.1088/1674-1056/22/6/060507