Graph Coloring: Comparing Cluster Graphs to Factor Graphs

Abstract

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.

References in corpus (1)

• A Probabilistic Graphical Model Approach to the Structure-and-Motion Problem

Cited by in corpus (2)

• Stochastic triangular mesh mapping: A terrain mapping technique for autonomous mobile robots
• Strengthening Probabilistic Graphical Models: The Purge-and-merge Algorithm