Collective dynamics of phase-repulsive oscillatorssolves graph coloring problem

Crnkić, Aladin (author), Povh, Janez (author), Jaćimović, Vladimir (author), Levnajić, Zoran (author)

We show how to couple phase-oscillators on a graph so that collective dynamics "searches" for the coloring of that graph as it relaxes toward the dynamical equilibrium. This translates a combinatorial optimization problem (graph coloring) into a functional optimization problem (finding and evaluating the global minimum of dynamical non-equilibrium potential, done by the natural system's evolution). Using a sample of graphs, we show that our method can serve as a viable alternative to the traditional combinatorial algorithms. Moreover, we show that, with the same computational cost, our method efficiently solves the harder problem of improper coloring of weighed graphs.

• Language: English
• Keywords: collective dynamics, graph coloring problem, functional optimization, dynamical equilibrium
• Work type: Article
• Typology: 1.01 - Original Scientific Article
• Organization: FS - Faculty of Mechanical Engineering
• Publication status: Published
• Publication version: Author Accepted Manuscript
• Year: 2020
• Number of pages: Str. 033128-1-033128-10
• Numbering: Vol. 30
• PID: 20.500.12556/RUL-114856
• UDC: 519.16(045)
• ISSN on article: 1054-1500
• DOI: 10.1063/1.5127794
• COBISS.SI-ID: 17094683
• Publication date in RUL: 20.03.2020

Secondary language

• Language: Slovenian
• Keywords: skupinska dinamika, problem barvanja grafa, funkcijska optimizacija, dinamično ravnovesje