| Article ID: | iaor20073093 |
| Country: | Germany |
| Volume: | 149 |
| Issue: | 1 |
| Start Page Number: | 67 |
| End Page Number: | 73 |
| Publication Date: | Feb 2007 |
| Journal: | Annals of Operations Research |
| Authors: | Werra D. de, Hammer Peter L. |
| Keywords: | history, graphs |
We exhibit links between pseudo-Boolean optimization, graph theory and logic. We show the equivalence of maximizing a pseudo-Boolean function and finding a maximum weight stable set; symmetrically minimizing a pseudo-Boolean function is shown to be equivalent to solving a weighted satisfiability problem.