A Parallel MCMC Algorithm for the Balanced Graph Coloring Problem

D. Conte, G. Grossi, R. Lanzarotti, Jianyi Lin, A. Petrini

Risultato della ricerca: Contributo in libroContributo a convegno

Abstract

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.
Lingua originaleEnglish
Titolo della pubblicazione ospiteLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Pagine161-171
Numero di pagine11
Volume11510
DOI
Stato di pubblicazionePubblicato - 2019
Evento12th IAPR-TC15 Workshop on Graph-Based Representations in Pattern Recognition, GbRPR 2019 - fra
Durata: 19 giu 201921 giu 2019

Serie di pubblicazioni

NomeLECTURE NOTES IN COMPUTER SCIENCE

Workshop

Workshop12th IAPR-TC15 Workshop on Graph-Based Representations in Pattern Recognition, GbRPR 2019
Cittàfra
Periodo19/6/1921/6/19

Keywords

  • Balanced graph coloring
  • Greedy colorer
  • Markov Chain Monte Carlo method
  • Parallel algorithms

Fingerprint

Entra nei temi di ricerca di 'A Parallel MCMC Algorithm for the Balanced Graph Coloring Problem'. Insieme formano una fingerprint unica.

Cita questo