Message passing for the coloring problem: Gallager meets Alon and Kahale
From MaRDI portal
Publication:3576765
zbMATH Open1192.68943arXiv0710.3928MaRDI QIDQ3576765
Sonny Ben-Shimon, Dan Vilenchik
Publication date: 2 August 2010
Abstract: 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 -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 -coloring of graphs drawn from a certain planted-solution distribution over -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.
Full work available at URL: https://arxiv.org/abs/0710.3928
This page was built for publication: Message passing for the coloring problem: Gallager meets Alon and Kahale
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3576765)
