Tractable Disjunctive Constraints Export

@inproceedings{cohen96tractable, abstract = {. Many combinatorial search problems can be expressed as `constraint satisfaction problems', and this class of problems is known to be NP-complete in general. In this paper we investigate `disjunctive constraints', that is, constraints which have the form of the disjunction of two constraints of specified types. We show that when the constraint types involved in the disjunction have a certain property, which we call `independence', and when a certain restricted class of problems is tractable,...}, author = {Cohen, D. A. and Jeavons, P. G. and Koubarakis, M.}, booktitle = {Proceedings 3rd International Conference on Constraint Programming---CP'97 (Linz, October 1997)}, citeulike-article-id = {709481}, citeulike-linkout-0 = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.25.8931}, keywords = {ai, csp}, pages = {478--490}, posted-at = {2006-06-24 08:50:21}, priority = {0}, publisher = {Springer-Verlag}, title = {Tractable Disjunctive Constraints}, url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.25.8931}, volume = {1330}, year = {1996} }

TY - CONF ID - cohen96tractable L3 - citeulike-article-id:709481 N2 - . Many combinatorial search problems can be expressed as `constraint satisfaction problems', and this class of problems is known to be NP-complete in general. In this paper we investigate `disjunctive constraints', that is, constraints which have the form of the disjunction of two constraints of specified types. We show that when the constraint types involved in the disjunction have a certain property, which we call `independence', and when a certain restricted class of problems is tractable,... EP - 490 TI - Tractable Disjunctive Constraints PB - Springer-Verlag VL - 1330 T2 - Proceedings 3rd International Conference on Constraint Programming---CP'97 (Linz, October 1997) SP - 478 KW - ai KW - csp AU - Cohen, DA AU - Jeavons, PG AU - Koubarakis, M PY - 1996/// UR - http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.25.8931 ER -