Classification of Bipartite Boolean Constraint Satisfaction through Delta-Matroid Intersection

DOI10.1137/S0895480104445009MaRDI QIDQ3440262zbMATH OpenOpenAlexFDO

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

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)

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

Cited in

(5)

• A strongly polynomial-time algorithm for weighted general factors with three feasible degrees
• 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)