×

A new oscillator coupling function for improving the solution of graph coloring problem. (English) Zbl 1486.05081

Summary: Conventional Boolean computational methods are inefficient in solving complex combinatorial optimization problems such as graph coloring or traveling sales man problem. In contrast, the dynamics of coupled oscillators could efficiently be used to find an optimal solution to such a class of problems. Kuramoto model is one of the most popular mathematical descriptions of coupled oscillators. However, the solution to the graph coloring problem using the Kuramoto model is not an easy task. The oscillators usually converge to a set of overlapping clusters. In this study, we mathematically derive a new coupling function that forces the oscillators to converge to a set of non-overlapping clusters with equal distance between classes. The proposed coupling function shows significant performance improvement compared to the original Kuramoto model.

MSC:

05C15 Coloring of graphs and hypergraphs
34C15 Nonlinear oscillations and coupled oscillators for ordinary differential equations
34D20 Stability of solutions to ordinary differential equations
70K20 Stability for nonlinear problems in mechanics
90C27 Combinatorial optimization

Software:

DIMACS
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Zhirnov, V. V.; Cavin, R. K.; Hutchby, J. A.; Bourianoff, G. I., Limits to binary logic switch scaling-a gedanken model, Proc. IEEE, 91, 11, 1934-1939 (2003)
[2] Theis, T. N.; Solomon, P. M., In quest of the “next switch”: prospects for greatly reduced power dissipation in a successor to the silicon field-effect transistor, Proc. IEEE, 98, 12, 2005-2014 (2010)
[3] Acebrón, J. A.; Bonilla, L. L.; Vicente, C. J.P.; Ritort, F.; Spigler, R., The Kuramoto model: A simple paradigm for synchronization phenomena, Rev. Modern Phys., 77, 1, 137 (2005)
[4] Kuramoto, Y., Chemical Oscillations, Waves, and Turbulence (2003), Courier Corporation
[5] Sakaguchi, H.; Kuramoto, Y., A soluble active rotater model showing phase transitions via mutual entertainment, Progr. Theoret. Phys., 76, 3, 576-581 (1986)
[6] Strogatz, S. H., From Kuramoto to Crawford: exploring the onset of synchronization in populations of coupled oscillators, Physica D, 143, 1-4, 1-20 (2000) · Zbl 0983.34022
[7] Wu, C. W., Graph coloring via synchronization of coupled oscillators, IEEE Trans. Circuits Syst. I, 45, 9, 974-978 (1998)
[8] Wu, J.; Jiao, L.; Li, R.; Chen, W., Clustering dynamics of nonlinear oscillator network: Application to graph coloring problem, Physica D, 240, 24, 1972-1978 (2011) · Zbl 1234.05107
[9] West, D. B., Introduction to Graph Theory, Vol. 2 (1996), Prentice Hall Upper Saddle River: Prentice Hall Upper Saddle River NJ · Zbl 0845.05001
[10] Leighton, F. T., A graph coloring algorithm for large scheduling problems, J. Res. Natl. Bur. Stand., 84, 6, 489-506 (1979) · Zbl 0437.68021
[11] Akers, S. B., Fault diagnosis as a graph coloring problem, IEEE Trans. Comput., 100, 7, 706-713 (1974) · Zbl 0281.94017
[12] Zufferey, N.; Amstutz, P.; Giaccari, P., Graph colouring approaches for a satellite range scheduling problem, J. Sched., 11, 4, 263-277 (2008) · Zbl 1168.90481
[13] Xizheng, Z.; Yaonan, W., New mixed broadcast scheduling approach using neural networks and graph coloring in wireless sensor network, J. Syst. Eng. Electron., 20, 1, 185-191 (2009)
[14] Woo, T.-K.; Su, S. Y.; Newman-Wolfe, R., Resource allocation in a dynamically partitionable bus network using a graph coloring algorithm, IEEE Trans. Commun., 39, 12, 1794-1801 (1991)
[15] (Johnson, D. J.; Trick, M. A., Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, Workshop. Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, Workshop, October 11-13, 1993 (1996), American Mathematical Society: American Mathematical Society Boston, MA, USA) · Zbl 0875.68678
[16] Parihar, A.; Shukla, N.; Jerry, M.; Datta, S.; Raychowdhury, A., Vertex coloring of graphs via phase dynamics of coupled oscillatory networks, Sci. Rep., 7, 1, 911 (2017)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.