Classification of Bipartite Boolean Constraint Satisfaction through Delta-Matroid Intersection

DOI10.1137/S0895480104445009zbMATH Open1115.68090OpenAlexW2004222819MaRDI QIDQ3440262FDOQ3440262

Authors:

Publication date: 22 May 2007

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

Recommendations

• Even delta-matroids and the complexity of planar Boolean CSPs
• Even delta-matroids and the complexity of planar Boolean CSPs
• Matching problems with delta-matroid constraints
• Parity systems and the delta-matroid intersection problem
• The linear delta-matroid parity problem

zbMATH Keywords

Boolean constraint satisfactionblossomsdelta matroids

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Model theory of finite structures (03C13)

Cited In (4)

• A Logical Approach to Constraint Satisfaction
• Colouring, constraint satisfaction, and complexity
• Even delta-matroids and the complexity of planar Boolean CSPs
• Even delta-matroids and the complexity of planar Boolean CSPs

This page was built for publication: Classification of Bipartite Boolean Constraint Satisfaction through Delta-Matroid Intersection

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