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

blossomsBoolean constraint satisfactiondelta matroids

Mathematics Subject Classification ID

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

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)

• Even delta-matroids and the complexity of planar Boolean CSPs
• Colouring, constraint satisfaction, and complexity
• Even delta-matroids and the complexity of planar Boolean CSPs
• A Logical Approach to Constraint Satisfaction
• A strongly polynomial-time algorithm for weighted general factors with three feasible degrees

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)