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

Simple item page
dc.creatorBen-Shimon, Sonny
dc.creatorVilenchik, Dan
dc.date2007-10-21
dc.date.accessioned2026-07-07T10:18:15Z
dc.date.available2026-07-07T10:18:15Z
dc.descriptionMessage passing algorithms are popular in many combinatorial optimization problems. For example, experimental results show that {\em survey 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. Our techniques can be applied to several other combinatorial optimization problems and networking-related issues.
dc.description11 pages
dc.identifierhttps://arxiv.org/abs/0710.3928
dc.identifierhttp://arxiv.org/abs/0710.3928
dc.identifierDMTCS Proceedings of the 13th Annual Conference on Analysis of Algorithms (AofA'07), Juan-les-pins, France, 2007. pp. 217--226.
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/174129
dc.subjectCombinatorics
dc.subjectDiscrete Mathematics
dc.subjectProbability
dc.titleMessage passing for the coloring problem: Gallager meets Alon and Kahale
dc.typetext

Files

Collections

arXiv