Experiments in the Dynamics of Phase Coupled Oscillators When Applied to Graph Colouring

Publisher:
Australian Computer Society, Inc
Publication Type:
Conference Proceeding
Citation:
31st Australasian Computer Science Conference (ACSC 2008), 2008, pp. 83 - 89
Issue Date:
2008-01
Full metadata record
Files in This Item:
Filename Description Size
Thumbnail2008000707.pdf833.22 kB
Adobe PDF
Abstract This paper examines the capacity of networks of phase coupled oscillators to coordinate activity in a parallel, distributed fashion. To benchmark these networks of oscillators, we present empirical results from a study of the capacity of such networks to colour graphs. We generalise the update equation of Aihara et al. (2006) to an equation that can be applied to graphs requiring multiple colours. We find that our simple multi-phase model can colour some types of graphs, especially complete graphs and complete k-partite graphs with equal or a near equal number of vertices in each partition. A surprising empirical result is that the effectiveness of the approach appears to be more dependent upon the topology of the graph than the size of the graph.
Please use this identifier to cite or link to this item: