izpis_h1_title_alt

Collective dynamics of phase-repulsive oscillatorssolves graph coloring problem
Crnkić, Aladin (Avtor), Povh, Janez (Avtor), Jaćimović, Vladimir (Avtor), Levnajić, Zoran (Avtor)

.pdfPDF - Predstavitvena datoteka, prenos (950,82 KB)
URLURL - Izvorni URL, za dostop obiščite https://aip.scitation.org/doi/10.1063/1.5127794 Povezava se odpre v novem oknu

Izvleček
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 (dk_c)
Tipologija:1.01 - Izvirni znanstveni članek
Organizacija:FS - Fakulteta za strojništvo
Leto izida:2020
Št. strani:str. 033128-1-033128-10
Številčenje:Vol. 30
UDK:519.16(045)
ISSN pri članku:1054-1500
DOI:10.1063/1.5127794 Povezava se odpre v novem oknu
COBISS.SI-ID:17094683 Povezava se odpre v novem oknu
Število ogledov:199
Število prenosov:185
Metapodatki:XML RDF-CHPDL DC-XML DC-RDF
 
Skupna ocena:(0 glasov)
Vaša ocena:Ocenjevanje je dovoljeno samo prijavljenim uporabnikom.
:
Objavi na:AddThis
AddThis uporablja piškotke, za katere potrebujemo vaše privoljenje.
Uredi privoljenje...

Gradivo je financirano iz projekta

Financer:ARRS - Agencija za raziskovalno dejavnost Republike Slovenije (ARRS)
Številka projekta:J1-8155
Naslov:ZLIVANJE BIOMEDICINSKIH PODATKOV Z UPORABO NENEGATIVNE MATRIČNETRI-FAKTORIZACIJE

Financer:ARRS - Agencija za raziskovalno dejavnost Republike Slovenije (ARRS)
Številka projekta:N1-0057
Naslov:Visoko zmogljiv reševalec za binarne kvadratične probleme

Financer:ARRS - Agencija za raziskovalno dejavnost Republike Slovenije (ARRS)
Številka projekta:N1-0071
Naslov:Razširitev algoritmov prvega in drugega reda za izbrane razrede optimizacijskih problemov s ciljem rešiti računsko zahtevne industrijske probleme

Financer:ARRS - Agencija za raziskovalno dejavnost Republike Slovenije (ARRS)
Številka projekta:P2-0256
Naslov:Konstruiranje

Sekundarni jezik

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

Podobna dela

Podobna dela v RUL:
Podobna dela v drugih slovenskih zbirkah:

Komentarji

Dodaj komentar

Za komentiranje se morate prijaviti.

Komentarji (0)
0 - 0 / 0
 
Ni komentarjev!

Nazaj