A. Billionnet and M. Minoux, Maximizing a supermodular pseudo-boolean function: a polynomial algorithm for supermodular cubic functions, Discrete Appl. Math, 1985.

E. Boros and P. L. Hammer, Pseudo-Boolean optimization, Discrete Applied Mathematics, vol.123, issue.1-3, pp.155-225, 2002.
DOI : 10.1016/S0166-218X(01)00341-9
URL : https://hal.archives-ouvertes.fr/hal-01150533

Y. Boykov, O. Veksler, and R. Zabih, Fast approximate energy minimization via graph cuts, PAMI, vol.23, issue.11, 2001.
DOI : 10.1109/iccv.1999.791245
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.112.6806

P. F. Felzenszwalb and D. P. Huttenlocher, Efficient belief propagation for early vision, Proceedings of the 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2004. CVPR 2004., pp.41-54, 2006.
DOI : 10.1109/CVPR.2004.1315041

B. Flach and D. Schlesinger, Best labelling search for a class of higher order Gibbs models, Pattern Recognition and Image Analysis, 2004.

D. Freedman and P. Drineas, Energy Minimization via Graph Cuts: Settling What is Possible, 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05), pp.939-946, 2005.
DOI : 10.1109/CVPR.2005.143
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.61.1348

G. Gallo, B. Simeone, and P. L. Hammer, On the supermodular knapsack problem Mathematical Programming: Series A and B Some network flow problems solved with pseudo-boolean programming, Operations Research, vol.45, issue.13, pp.295-309388, 1965.

D. Hoiem, A. A. Efros, and M. Hebert, Recovering Surface Layout from an Image, International Journal of Computer Vision, vol.63, issue.2, pp.151-172, 2007.
DOI : 10.1007/s11263-006-0031-y
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.220.2180

H. Ishikawa, Exact optimization for markov random fields with convex priors, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.25, issue.10, pp.1333-1336, 2003.
DOI : 10.1109/TPAMI.2003.1233908

P. Kohli, L. Ladicky, and P. H. Torr, Graph cuts for minimizing robust higher order potentials, 2008.

P. Kohli, L. Ladicky, and P. H. Torr, Robust higher order potentials for enforcing label consistency, CVPR, 2008.

V. Kolmogorov and R. Zabih, What energy functions can be minimized via graph cuts? PAMI, 2004.
DOI : 10.1109/tpami.2004.1262177
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.113.1823

X. Lan, S. Roth, D. P. Huttenlocher, and M. J. Black, Efficient Belief Propagation with Learned Higher-Order Markov Random Fields, ECCV, pp.269-282, 2006.
DOI : 10.1109/TIP.2003.819861
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.70.8126

A. Levin, A. Zomet, S. Peleg, and Y. Weiss, Seamless image stiching in the gradient domain, ECCV, 2004.

J. B. Orlin, A faster strongly polynomial time algorithm for submodular function minimization, IPCO, 2007.

B. Potetz, Efficient Belief Propagation for Vision Using Linear Constraint Nodes, 2007 IEEE Conference on Computer Vision and Pattern Recognition, 2007.
DOI : 10.1109/CVPR.2007.383094

S. Ramalingam, P. Kohli, K. Alahari, and P. H. Torr, Transforming multi-label higher order crfs to binary pairwise ones, 2008.
DOI : 10.1109/cvpr.2008.4587401
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.188.579

I. G. Rosenberg, Reduction of bivalent maximization to the quadratic case, pp.71-74, 1975.

S. Roth and M. J. Black, Fields of Experts: A Framework for Learning Image Priors, 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05), 2005.
DOI : 10.1109/CVPR.2005.160

C. Rother, V. Kolmogorov, V. Lempitsky, and M. Szummer, Optimizing Binary MRFs via Extended Roof Duality, 2007 IEEE Conference on Computer Vision and Pattern Recognition, 2007.
DOI : 10.1109/CVPR.2007.383203
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.63.4613

D. Scharstein and R. Szeliski, A taxonomy and evaluation of dense two-frame stereo correspondence algorithms, Proceedings IEEE Workshop on Stereo and Multi-Baseline Vision (SMBV 2001), pp.7-42, 2002.
DOI : 10.1109/SMBV.2001.988771

D. Schlesinger, Exact Solution of Permuted Submodular MinSum Problems, EMMCVPR, pp.28-38, 2007.
DOI : 10.1007/978-3-540-74198-5_3

D. Schlesinger and B. Flach, Transforming an arbitrary minsum problem into a binary one, 2006.

O. Veksler, Graph Cut Based Optimization for MRFs with Truncated Convex Priors, 2007 IEEE Conference on Computer Vision and Pattern Recognition, 2007.
DOI : 10.1109/CVPR.2007.383249

M. J. Wainwright, T. Jaakkola, and A. S. Willsky, Treebased reparameterization for approximate inference on loopy graphs, NIPS, pp.1001-1008, 2001.

Z. Yang and D. Purves, Image/source statistics of surfaces in natural scenes, Network: Computation in Neural Systems, vol.14, issue.3, 2003.
DOI : 10.1088/0954-898X_14_3_301

J. S. Yedidia, W. T. Freeman, and Y. Weiss, Generalized belief propagation [30] B. Zalesky. Efficient determination of gibbs estimators with submodular energy functions, NIPS, pp.689-695, 2000.