A new oscillator coupling function for improving the solution of graph coloring problem

PHYSICA D-NONLINEAR PHENOMENA

卷:412

Article

Andrawis, Robert¹  Roy, Kaushik¹ 

[1] Purdue Univ, Sch Elect & Comp Engn, W Lafayette, IN 47906 USA

关键词: Kuramoto model;    Graph coloring;    Coupled oscillators;   

DOI  :  10.1016/j.physd.2020.132617

来源: Elsevier

【 摘 要 】

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. (C) 2020 Elsevier B.V. All rights reserved.

【 授权许可】

Free