Complexity of minimum-size arc-inconsistency explanations

DOI10.1007/S10601-023-09360-5MaRDI QIDQ6154178zbMATH OpenFDO

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

Publication date 14 February 2024

Published in Constraints (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S10601-023-09360-5

zbMATH Keywords

complexityconstraint programmingconstraint propagationminimum explanations

Mathematics Subject Classification ID

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

Cites work

• A birthday repetition theorem and complexity of approximating dense CSPs
• A framework for step-wise explaining how to solve constraint satisfaction problems
• Completely inapproximable monotone and antimonotone parameterized problems
• Consistency restoration and explanations in dynamic CSPs---Application to configuration
• From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more
• Handbook of constraint programming.
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• On Parameterized Approximability
• Parametrized complexity theory.
• Reducibility among combinatorial problems

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6154178)