Discovering archipelagos of tractability for constraint satisfaction and counting

DOI10.1137/1.9781611974331.CH114zbMATH Open1410.68166OpenAlexW4299565076MaRDI QIDQ4575698FDOQ4575698

Authors: Robert Ganian, M. S. Ramanujan, Stefan Szeider 

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611974331.ch114

Recommendations

• Discovering archipelagos of tractability for constraint satisfaction and counting
• Backdoor sets for CSP
• Combining treewidth and backdoors for CSP
• Tractability in constraint satisfaction problems: a survey
• Tractability by approximating constraint languages

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25)

Cited In (6)

• CSP beyond tractable constraint languages
• Backdoors into heterogeneous classes of SAT and CSP
• Backdoor sets for CSP
• Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems
• Combining treewidth and backdoors for CSP
• Discovering archipelagos of tractability for constraint satisfaction and counting

This page was built for publication: Discovering archipelagos of tractability for constraint satisfaction and counting

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