A note on some collapse results of valued constraints

DOI10.1016/j.ipl.2009.01.018zbMath1214.68377OpenAlexW2046699448MaRDI QIDQ987814

Bruno Zanuttini, Stanislav Živný

Publication date: 16 August 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2009.01.018

zbMATH Keywords

expressive powervalued constraint satisfaction problemsmax-closed constraints

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Classes of submodular constraints expressible by graph cuts
• High-order consistency in valued constraint satisfaction
• The expressive power of valued constraints: Hierarchies and collapses
• On the algebraic structure of combinatorial problems
• Semiring-based CSPs and valued CSPs: Frameworks, properties, and comparison
• Networks of constraints: Fundamental properties and applications to picture processing
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• The complexity of soft constraint satisfaction
• The Approximability of Constraint Satisfaction Problems
• Complexity Classifications of Boolean Constraint Satisfaction Problems
• The Expressive Power of Binary Submodular Functions
• An Algebraic Characterisation of Complexity for Valued Constraint
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• Efficient Algorithms for Description Problems over Finite Totally Ordered Domains
• Classifying the Complexity of Constraints Using Finite Algebras
• Tractable constraints on ordered domains

This page was built for publication: A note on some collapse results of valued constraints