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

Mathematics – Combinatorics

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

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.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

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.

Rate now

     

Profile ID: LFWR-SCP-O-210486

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.