Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > DELTA-MATROID INTERSECTION:
Reports tagged with delta-matroid intersection:
TR05-016 | 13th January 2005
Tomas Feder, Daniel Ford

Classification of Bipartite Boolean Constraint Satisfaction through Delta-Matroid Intersection

Matroid intersection has a known polynomial time algorithm using an
oracle. We generalize this result to delta-matroids that do not have
equality as a restriction, and give a polynomial time algorithm for
delta-matroid intersection on delta-matroids without equality using an
oracle. We note that when equality is present, delta-matroid intersection
more >>>




ISSN 1433-8092 | Imprint