An efficient algorithm for a class of constraint satisfaction problems

Gerhard J. Woeginger

Research output: Contribution to journalArticleAcademicpeer-review

7 Citations (Scopus)

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.
Original languageEnglish
Pages (from-to)9-16
JournalOperations research letters
Volume30
Issue number1
DOIs
Publication statusPublished - 2002

Keywords

  • Efficient algorithm
  • Satisfiability
  • Feasibility checking
  • Horn formula
  • Graph homomorphism
  • Graph coloring
  • Monotone integer programming
  • AND/OR project scheduling
  • Constraint satisfaction
  • IR-74835
  • METIS-208615

Fingerprint Dive into the research topics of 'An efficient algorithm for a class of constraint satisfaction problems'. Together they form a unique fingerprint.

Cite this