k-Phase Oscillator Synchronization for Graph Coloring

Birkhauser Basel
Publication Type:
Journal Article
Mathematics in Computer Science, 2010, 3, 1, pp. 323 - 342
Issue Date:
Filename Description Size
Thumbnail2009000478OK.pdf357.87 kB
Adobe PDF
Full metadata record
This paper investigates ways of applying oscillator synchronization to graph coloring. A previous method based on the generalization of the Aihara model is sensitive to the varying degree of the vertices in the graph and there is a strong tendency for the network to form suboptimal limit cycles on regular graphs. Other models such as those by Wu and Nakaguchi, Jinâno and Tanaka do not generalize well into greater than 2-coloring. In this paper, we present ways to overcome these problems and describe the results of our experiments on graphs requiring more than two colors. Our k-phase model enhances the coloring performance over the previous similar models. We further attempt to formalize and analyze the categorical behavior of these systems and discuss connections to other optimization methods.
Please use this identifier to cite or link to this item: