|
 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.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
Aihara, I., Kitahata, H., Aihara, K. & Yoshikawa, K. 2006, Periodic rhythms and anti-phase synchronization in calling behaviours of Japanese rain frogs, University of Tokyo, http://www.i.u-tokyo.ac.jp/mi/mi-e.htm, viewed 18 September 2006.
|
| |
2
|
Bennett, M., Schatz, M. F., Rockwood, H. & Wiesenfeld, K. 2002, 'Huygens' clocks', Proceedings (A) of the Royal Society, vol. 458, pp. 563--579.
|
| |
3
|
Bettstetter, C. 2006, Self-Organization in Communication Networks, www.bettstetter.com/talks/bettstetter-so-2006-06-passau.pdf viewed 18 September 2006.
|
| |
4
|
Buck, E. & Buck, J. 1976, 'Synchronous fireflies', Scientific American, no. 234, pp. 74--85.
|
| |
5
|
Buck, J., Buck, E., Case, J. F. & Hanson, F. E. 1981, 'Control of flashing in fireflies. V. Pacemaker Synchronization in Pteroptyx cribellata', Journal of comparative physiology A, vol. 144, no. 3, pp. 287--298.
|
| |
6
|
Scott Camazine , Nigel R. Franks , James Sneyd , Eric Bonabeau , Jean-Louis Deneubourg , Guy Theraula, Self-Organization in Biological Systems, Princeton University Press, Princeton, NJ, 2001
|
| |
7
|
Ermentrout, G. B. & Rinzel, J. 1984, 'Beyond a pacemaker's entrainment limit: phase walk-through', American Journal of Physiology - Regulatory, Integrative and Comparative Physiology, vol. 246, no. 1, pp. 102--106.
|
| |
8
|
|
| |
9
|
Hong, Y. W. & Scaglione, A. 2003, 'Time synchronization and reach-back communications with pulse-coupled oscillators for UWB wireless ad hoc networks', Proceedings of the IEEE conference on Ultra Wideband Systems and Technologies, Reston, VA, pp. 190--194.
|
| |
10
|
Hopfield, J. J. & Tank, D. W. 1985, 'Neural computation of decisions in optimization problems', Biological Cybernetics, no. 52, pp. 141--152.
|
| |
11
|
Kindermann, R. and Snell, J. L. (1980) Random Markov Fields and Their Applications, American Mathematical Society, ISBN 0-8218-3381-2.
|
| |
12
|
Kuramoto, Y. 1984, Chemical Oscillations, Waves and Turbolence, Spinger, Berlin.
|
| |
13
|
Lister, R. 1992, 'On making the right moves: Neural networks, gradient descent and simulated annealing', Unpublished PhD Thesis, Basser Department of Computer Science, The University of Sydney, Sydney.
|
 |
14
|
|
| |
15
|
|
| |
16
|
Spong, M. W. 2006, 'Coordination of multi-agent systems', The eight IASTED international conference on control and applications, ed. C. Y. Su, Montreal, Canada, pp. 10--16.
|
| |
17
|
|
| |
18
|
Geoffrey Werner-Allen , Geetika Tewari , Ankit Patel , Matt Welsh , Radhika Nagpal, Firefly-inspired sensor network synchronicity with realistic radio effects, Proceedings of the 3rd international conference on Embedded networked sensor systems, November 02-04, 2005, San Diego, California, USA
[doi> 10.1145/1098918.1098934]
|
| |
19
|
Wu, C. W. 2002, Synchronization in coupled chaotic circuits and systems, World Scientific Publishing Co, Singapore.
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf