Even delta-matroids and the complexity of planar Boolean CSPs

DOI10.1137/1.9781611974782.20zbMATH Open1410.68170OpenAlexW2949835687MaRDI QIDQ4575757FDOQ4575757

Authors: Alexandr Kazda, Vladimir Kolmogorov, Michal Rolínek 

Publication date: 16 July 2018

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

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

Recommendations

• Even delta-matroids and the complexity of planar Boolean CSPs
• Classification of Bipartite Boolean Constraint Satisfaction through Delta-Matroid Intersection
• The linear delta-matroid parity problem
• Matchings and \(\Delta\)-matroids with coefficients
• Matching problems with delta-matroid constraints

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial aspects of matroids and geometric lattices (05B35)

Cited In (6)

• Classification of Bipartite Boolean Constraint Satisfaction through Delta-Matroid Intersection
• On the Complexity of Holant Problems
• Hybrid tractable classes of constraint problems
• On planar valued CSPs
• Even delta-matroids and the complexity of planar Boolean CSPs
• On Planar Boolean CSP

This page was built for publication: Even delta-matroids and the complexity of planar Boolean CSPs

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