20.500.12556/RUL-114856
Collective dynamics of phase-repulsive oscillatorssolves graph coloring problem
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.
collective dynamics
graph coloring problem
functional optimization
dynamical equilibrium
skupinska dinamika
problem barvanja grafa
funkcijska optimizacija
dinamično ravnovesje
true
false
true
Angleški jezik
Slovenski jezik
Članek v reviji
2020-03-20 09:35:40
2020-03-20 09:35:42
2022-08-27 03:58:16
0000-00-00 00:00:00
2020
0
0
Str. 033128-1-033128-10
Vol. 30
2020
0000-00-00
PostprintKoncna
Objavljeno
NiDoloceno
0000-00-00
0000-00-00
0000-00-00
519.16(045)
1054-1500
10.1063/1.5127794
17094683
RAZ_Crnkic_Aladin_2020.pdf
RAZ_Crnkic_Aladin_2020.pdf
1
4BFC2AA9F5555E6C4DEF591B1318626C
7e79969f2de2f850b0d3e0555f623f4b3a3c6d4593fa4d49cea1e818a19d8023
4c73f90e-a1b8-11eb-a523-00155dcfd717
https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=127286
https://aip.scitation.org/doi/10.1063/1.5127794
1
https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=127182
Fakulteta za strojništvo
0
0
0