Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadata

Cited literature [22 references]  Display  Hide  Download
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Monday, August 17, 2015 - 5:00:07 PM
Last modification on : Thursday, May 11, 2017 - 1:03:04 AM
Long-term archiving on: : Wednesday, November 18, 2015 - 12:18:02 PM


Publisher files allowed on an open archive




Sonny Ben-Shimon, Dan Vilenchik. Message passing for the coloring problem: Gallager meets Alon and Kahale. 2007 Conference on Analysis of Algorithms, AofA 07, 2007, Juan les Pins, France. pp.235-246, ⟨10.46298/dmtcs.3546⟩. ⟨hal-01184794⟩



Record views


Files downloads