Complexity of minimum-size arc-inconsistency explanations

DOI10.1007/s10601-023-09360-5MaRDI QIDQ6154178

Clément Carbonnel, Emmanuel Hebrard, Christian Bessiere, Martin C. Cooper

Publication date: 14 February 2024

Published in: Constraints (Search for Journal in Brave)

zbMATH Keywords

complexityconstraint propagationconstraint programmingminimum explanations

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Theory of computing (68Qxx) Discrete mathematics in relation to computer science (68Rxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Completely inapproximable monotone and antimonotone parameterized problems
• A framework for step-wise explaining how to solve constraint satisfaction problems
• Parametrized complexity theory.
• On Parameterized Approximability
• Reducibility among Combinatorial Problems
• From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More
• Consistency restoration and explanations in dynamic CSPs---Application to configuration

This page was built for publication: Complexity of minimum-size arc-inconsistency explanations