Graph Coloring: Comparing Cluster Graphs to Factor Graphs
This work addresses graph coloring for researchers in probabilistic modeling and optimization, offering a novel method that outperforms existing factor graph approaches.
The paper tackled graph coloring problems by proposing a probabilistic graphical model approach using cluster graphs instead of factor graphs, and introduced the LTRIP algorithm for automatic cluster graph construction, resulting in significant improvements in accuracy and computational efficiency.
We present a means of formulating and solving graph coloring problems with probabilistic graphical models. In contrast to the prevalent literature that uses factor graphs for this purpose, we instead approach it from a cluster graph perspective. Since there seems to be a lack of algorithms to automatically construct valid cluster graphs, we provide such an algorithm (termed LTRIP). Our experiments indicate a significant advantage for preferring cluster graphs over factor graphs, both in terms of accuracy as well as computational efficiency.