Collective dynamics of phase-repulsive oscillatorssolves graph coloring problem

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

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.

• Jezik: Angleški jezik
• Ključne besede: collective dynamics, graph coloring problem, functional optimization, dynamical equilibrium
• Vrsta gradiva: Članek v reviji
• Tipologija: 1.01 - Izvirni znanstveni članek
• Organizacija: FS - Fakulteta za strojništvo
• Status publikacije: Objavljeno
• Različica publikacije: Recenzirani rokopis
• Leto izida: 2020
• Št. strani: Str. 033128-1-033128-10
• Številčenje: Vol. 30
• PID: 20.500.12556/RUL-114856
• UDK: 519.16(045)
• ISSN pri članku: 1054-1500
• DOI: 10.1063/1.5127794
• COBISS.SI-ID: 17094683
• Datum objave v RUL: 20.03.2020

Sekundarni jezik

• Jezik: Slovenski jezik
• Ključne besede: skupinska dinamika, problem barvanja grafa, funkcijska optimizacija, dinamično ravnovesje