Dynamic algorithms for classes of constraint satisfaction problems

DOI10.1016/S0304-3975(00)00013-XMaRDI QIDQ5941281zbMATH OpenOpenAlexFDO

Authors Daniele Frigioni, Alberto Marchetti-Spaccamela, Umberto Nanni

Publication date 20 August 2001

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0304-3975(00)00013-x

zbMATH Keywords

amortized complexitybacktrack-free searchconsistencyconstraint satisfaction problemdynamic algorithmsnetwork of constraints

Mathematics Subject Classification ID

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

Recommendations

• Computational Complexity of Constraint Satisfaction
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• Constraint satisfaction problems: Algorithms and applications
• Constraint updating
• Complexity of conservative constraint satisfaction problems

Cites work

• A sufficient condition for backtrack-bounded search
• A Sufficient Condition for Backtrack-Free Search
• Amortized Computational Complexity
• Approximation of Constraint Satisfaction via local search
• Consistency in networks of relations
• Constraint relaxation may be perfect
• Fast parallel constraint satisfaction
• scientific article; zbMATH DE number 1002207 (Why is no real title available?)
• scientific article; zbMATH DE number 4049150 (Why is no real title available?)
• scientific article; zbMATH DE number 3758364 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Minimal Representation of Directed Hypergraphs
• Network-based heuristics for constraint-satisfaction problems
• Networks of constraints: Fundamental properties and applications to picture processing
• Synthesizing constraint expressions

Cited in

(6)

• An efficient algorithm for a class of constraint satisfaction problems
• Nature-inspired techniques for dynamic constraint satisfaction problems
• scientific article; zbMATH DE number 1670594 (Why is no real title available?)
• Dynamic Management of Heuristics for Solving Structured CSPs
• Constraint updating
• scientific article; zbMATH DE number 2152986 (Why is no real title available?)

This page was built for publication: Dynamic algorithms for classes of constraint satisfaction problems

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