TY - GEN
T1 - A Parallel MCMC Algorithm for the Balanced Graph Coloring Problem
AU - Conte, D.
AU - Grossi, G.
AU - Lanzarotti, R.
AU - Lin, Jianyi
AU - Petrini, A.
PY - 2019
Y1 - 2019
N2 - In parallel computation domain, graph coloring is widely studied in its own and represents a reference problem for scheduling of parallel tasks. Unfortunately, common graph coloring strategies usually focus on minimizing the number of colors without any concern for the sizes of each color class, thus producing highly skewed color class distributions. However, to guarantee efficiency in parallel computations, but also in other application contexts, it is important to keep the color classes highly balanced in their sizes. In this paper we address this challenging issue for large scale graphs, proposing a fast parallel MCMC heuristic for sparse graphs that randomly generates good balanced colorings provided that a sufficient number of colors are made available. We show its effectiveness through some numerical simulations on random graphs.
AB - In parallel computation domain, graph coloring is widely studied in its own and represents a reference problem for scheduling of parallel tasks. Unfortunately, common graph coloring strategies usually focus on minimizing the number of colors without any concern for the sizes of each color class, thus producing highly skewed color class distributions. However, to guarantee efficiency in parallel computations, but also in other application contexts, it is important to keep the color classes highly balanced in their sizes. In this paper we address this challenging issue for large scale graphs, proposing a fast parallel MCMC heuristic for sparse graphs that randomly generates good balanced colorings provided that a sufficient number of colors are made available. We show its effectiveness through some numerical simulations on random graphs.
KW - Balanced graph coloring
KW - Greedy colorer
KW - Markov Chain Monte Carlo method
KW - Parallel algorithms
KW - Balanced graph coloring
KW - Greedy colorer
KW - Markov Chain Monte Carlo method
KW - Parallel algorithms
UR - http://hdl.handle.net/10807/178250
U2 - 10.1007/978-3-030-20081-7_16
DO - 10.1007/978-3-030-20081-7_16
M3 - Conference contribution
SN - 978-3-030-20080-0
VL - 11510
T3 - LECTURE NOTES IN COMPUTER SCIENCE
SP - 161
EP - 171
BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
T2 - 12th IAPR-TC15 Workshop on Graph-Based Representations in Pattern Recognition, GbRPR 2019
Y2 - 19 June 2019 through 21 June 2019
ER -