Mathematics – Combinatorics
Scientific paper
2007-10-21
DMTCS Proceedings of the 13th Annual Conference on Analysis of Algorithms (AofA'07), Juan-les-pins, France, 2007. pp. 217--226
Mathematics
Combinatorics
11 pages
Scientific paper
Message 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.
Ben-Shimon Sonny
Vilenchik Dan
No associations
LandOfFree
Message passing for the coloring problem: Gallager meets Alon and Kahale does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Message passing for the coloring problem: Gallager meets Alon and Kahale, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Message passing for the coloring problem: Gallager meets Alon and Kahale will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-210486