# An efficient algorithm for a class of constraint satisfaction problems

Woeginger, Gerhard J.
(2002)
*An efficient algorithm for a class of constraint satisfaction problems.*
Operations Research Letters, 30
(1).
pp. 9-16.
ISSN 0167-6377

PDF
Restricted to UT campus only : Request a copy 140kB |

Abstract: | We define the class of the so-called monotone constraint satisfaction problems (MON-CSP). MON-CSP forms a subclass of the class of min-closed (respectively, max-closed) constraint satisfaction problems of Jeavons and Cooper (Artificial Intelligence 79 (1995) 327). We prove that for all problems in the class MON-CSP there exists a very fast and very simple algorithm for testing feasibility.
We then show that a number of well-known results from the literature are special cases of MON-CSP: (1) Satisfiability of Horn formulae; (2) graph homomorphisms to directed graphs with an -numbering; (3) monotone integer programming with two variables per inequality; (4) project scheduling under AND/OR precedence constraints. Our results provide a unified algorithmic approach to all these problems. |

Item Type: | Article |

Copyright: | © 2002 Elsevier |

Faculty: | Electrical Engineering, Mathematics and Computer Science (EEMCS) |

Research Group: | |

Link to this item: | http://purl.utwente.nl/publications/74835 |

Official URL: | http://dx.doi.org/10.1016/S0167-6377(01)00114-6 |

Export this item as: | BibTeX EndNote HTML Citation Reference Manager |

Repository Staff Only: item control page

Metis ID: 208615