Message passing for the coloring problem: Gallager meets Alon and Kahale

Abstract : Message passing algorithms are popular in many combinatorial optimization problems. For example, experimental results show that \emphsurvey propagation (a certain message passing algorithm) is effective in finding proper k-colorings of random graphs in the near-threshold regime. In 1962 Gallager introduced the concept of Low Density Parity Check (LDPC) codes, and suggested a simple decoding algorithm based on message passing. In 1994 Alon and Kahale exhibited a coloring algorithm and proved its usefulness for finding a k-coloring of graphs drawn from a certain planted-solution distribution over k-colorable graphs. In this work we show an interpretation of Alon and Kahale's coloring algorithm in light of Gallager's decoding algorithm, thus showing a connection between the two problems - coloring and decoding. This also provides a rigorous evidence for the usefulness of the message passing paradigm for the graph coloring problem.
Type de document :
Communication dans un congrès
Jacquet, Philippe. 2007 Conference on Analysis of Algorithms, AofA 07, 2007, Juan les Pins, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07), pp.235-246, 2007, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [22 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01184794
Contributeur : Coordination Episciences Iam <>
Soumis le : lundi 17 août 2015 - 17:00:07
Dernière modification le : jeudi 11 mai 2017 - 01:03:04
Document(s) archivé(s) le : mercredi 18 novembre 2015 - 12:18:02

Fichier

dmAH0115.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01184794, version 1

Collections

Citation

Sonny Ben-Shimon, Dan Vilenchik. Message passing for the coloring problem: Gallager meets Alon and Kahale. Jacquet, Philippe. 2007 Conference on Analysis of Algorithms, AofA 07, 2007, Juan les Pins, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07), pp.235-246, 2007, DMTCS Proceedings. 〈hal-01184794〉

Partager

Métriques

Consultations de la notice

60

Téléchargements de fichiers

158