Skip to main content

Minimal Weighted Clones with Boolean Support

Peter G. Jeavons‚ Andrius Vaicenavičius and Stanislav Živný

Abstract

We study algebraic structures called weighted clones. These structures characterise the computational complexity of discrete optimisation problems of special form, known as valued constraint satisfaction problems. We identify all minimal weighted clones for every Boolean support clone.

Book Title
Proceedings of the 46th IEEE International Symposium on Multiple−Valued Logic‚ ISMVL 2016‚ Sapporo‚ Japan‚ May 18−20‚ 2016
Editor
Takahiro Hanyu
Month
May
Pages
90–95
Publisher
IEEE Computer Society
Year
2016