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

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 int...

Full description

Bibliographic Details
Main Authors: Sonny Ben-Shimon, Dan Vilenchik
Format: Article
Language:English
Published: Discrete Mathematics & Theoretical Computer Science 2007-01-01
Series:Discrete Mathematics & Theoretical Computer Science
Subjects:
Online Access:https://dmtcs.episciences.org/3546/pdf