Skip to main content

Research Repository

Advanced Search

The complexity of Valued CSPs

Krokhin, A.; Živný, S.

The complexity of Valued CSPs Thumbnail


Authors

S. Živný



Contributors

S. Živný
Editor

Abstract

We survey recent results on the broad family of problems that can be cast as valued constraint satisfaction problems (VCSPs). We discuss general methods for analysing the complexity of such problems, give examples of tractable cases, and identify general features of the complexity landscape.

Citation

Krokhin, A., & Živný, S. (2017). The complexity of Valued CSPs. In A. Krokhin, & S. Živný (Eds.), The constraint satisfaction problem : complexity and approximability (233-266). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/dfu.vol7.15301.9

Publication Date Jan 1, 2017
Deposit Date Mar 9, 2017
Publicly Available Date Mar 29, 2024
Publisher Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Pages 233-266
Series Title Dagstuhl follow-ups
Book Title The constraint satisfaction problem : complexity and approximability.
Chapter Number 9
DOI https://doi.org/10.4230/dfu.vol7.15301.9

Files





You might also like



Downloadable Citations