Izvorni znanstveni članak

https://doi.org/10.17535/crorr.2024.0009

A fresh look at a randomized massively parallel graph coloring algorithm

Boštjan Gabrovšek ; University of Ljubljana, Faculty of Mechanical Engineering, Aškerčeva 6, 1000 Ljubljana, Slovenia / Institute of Mathematics, Physics and Mechanics, Jadranska ulica 19, 1000 Ljubljana, Slovenia
Janez Žerovnik orcid.org/0000-0002-6041-1106 ; University of Ljubljana, Faculty of Mechanical Engineering, Aškerčeva 6, 1000 Ljubljana, Slovenia / Rudolfovo – Science and Technology Centre Novo mesto, Podbreznik 15, 8000 Novo mesto, Slovenia *

* Dopisni autor.

Sažetak

Petford and Welsh introduced a sequential heuristic algorithm to provide an approximate solution to the NP-hard graph coloring problem. The algorithm is based on the antivoter model and mimics the behavior of a physical process based on a multi-particle system of statistical mechanics. It was later shown that the algorithm can be implemented in a massively parallel model of computation. The increase in computational processing power in recent years allows us to perform an extensive analysis of the algorithms on a larger scale, leading to the possibility of a more comprehensive understanding of the behavior of the algorithm, including the phase transition phenomena.

Ključne riječi

combinatorial optimization; graph coloring; randomized local search procedure; temperature

Hrčak ID:

321254

URI

https://hrcak.srce.hr/321254

Datum izdavanja:

7.10.2024.

Posjeta: 163 *