Abstract: Chapter 4 focuses on the expressive power of binary submodular functions. Known and new classes of submodular functions that are expressible by binary submodular functions are presented. There is a close relationship between the expressive power of binary submodular functions and solving submodular valued constraint satisfaction problems via the minimum cut problem: showing that a class $\mathcal{C}$ of submodular functions is expressible by binary submodular functions is equivalent to showing that functions from $\mathcal{C}$ can be minimised efficiently via the minimum cut problem.
Publication Year: 2012
Publication Date: 2012-01-01
Language: en
Type: book-chapter
Indexed In: ['crossref']
Access and Citation
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot