Discovering archipelagos of tractability for constraint satisfaction and counting

DOI10.1137/1.9781611974331.CH114MaRDI QIDQ4575698zbMATHOpenAlexFDO

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

Mathematics Subject Classification ID

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

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

Cited in

(6)

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

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)