Original scientific paper
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
*
* Corresponding author.
Abstract
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.
Keywords
combinatorial optimization; graph coloring; randomized local search procedure; temperature
Hrčak ID:
321254
URI
Publication date:
7.10.2024.
Visits: 132 *