Geodesic
Message passing for the coloring problem: Gallager meets Alon and Kahale
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07), DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07) (2007).

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2007_special_253_a28,
     author = {Ben-Shimon, Sonny and Vilenchik, Dan},
     title = {Message passing for the coloring problem: {Gallager} meets {Alon} and {Kahale}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07)},
     year = {2007},
     doi = {10.46298/dmtcs.3546},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3546/}
}
TY  - JOUR
AU  - Ben-Shimon, Sonny
AU  - Vilenchik, Dan
TI  - Message passing for the coloring problem: Gallager meets Alon and Kahale
JO  - Discrete mathematics & theoretical computer science
PY  - 2007
VL  - DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07)
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3546/
DO  - 10.46298/dmtcs.3546
LA  - en
ID  - DMTCS_2007_special_253_a28
ER  - 
%0 Journal Article
%A Ben-Shimon, Sonny
%A Vilenchik, Dan
%T Message passing for the coloring problem: Gallager meets Alon and Kahale
%J Discrete mathematics & theoretical computer science
%D 2007
%V DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07)
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3546/
%R 10.46298/dmtcs.3546
%G en
%F DMTCS_2007_special_253_a28
Ben-Shimon, Sonny; Vilenchik, Dan. Message passing for the coloring problem: Gallager meets Alon and Kahale. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07), DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07) (2007). doi : 10.46298/dmtcs.3546. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3546/

Cité par Sources :