Point-Width and Max-CSPs

DOI10.1145/3409447MaRDI QIDQ5888946zbMATH OpenOpenAlexFDO

Authors Clément Carbonnel, Miguel Romero, S. Zivny

Publication date 26 April 2023

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1904.07388

zbMATH Keywords

constraint satisfactionhypergraphsmaximum constraint satisfactionhypertree width\(\beta\)-acyclicity

Mathematics Subject Classification ID

Computer science (68-XX)

Recommendations

• Point-width and max-CSPs
• Beyond Hypertree Width: Decomposition Methods Without Decompositions
• Tractable hypergraph properties for constraint satisfaction and conjunctive queries
• Tractable hypergraph properties for constraint satisfaction and conjunctive queries
• Tractable structures for constraint satisfaction with truth tables

Cited in

(4)

• Tractability beyond -acyclicity for conjunctive queries with negation and SAT
• Parameterized approximation for maximum weight independent set of rectangles and segments
• Point-width and max-CSPs
• Direct access for conjunctive queries with negations

This page was built for publication: Point-Width and Max-CSPs

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