Professor David Cohen

  1. Paper › Research › Not peer-reviewed
  2. Published

    Typed Guarded Decompositions for Constraint Satisfaction

    Cohen, D. A. & Green, M. J., 2006, p. 122-136.

    Research output: Contribution to conferencePaper

  3. Conference contribution › Research
  4. Published

    A Substitution Operation for Constraints

    Jeavons, P. G., Cohen, D. A. & Cooper, M. C., 1 May 1994, Principles and Practice of Constraint Programming: Second International Workshop, PPCP '94 Rosario, Orcas Island, WA, USA, May 2–4, 1994 Proceedings. Borning, A. (ed.). Vol. 874. p. 1-9

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  5. Published

    An Algebraic Theory of Complexity for Valued Constraints: Establishing a Galois Connection

    Cohen, D. A., Creed, P., Jeavons, P. G. & Živný, S., 2011, Mathematical Foundations of Computer Science 2011: 36th International Symposium, MFCS 2011, Warsaw, Poland, August 22-26, 2011: Proceedings. Springer, p. 231-242 (Lecture Notes in Computer Science; vol. 6907).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  6. Published

    Engineering Algorithms for Workflow Satisfiability Problem with User-Independent Constraints

    Cohen, D., Crampton, J., Gagarin, A., Gutin, G. & Jones, M., 2014, FAW 2014. (Lecture Notes in Computer Science; vol. 8497).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  7. Published

    On Singleton Arc Consistency for CSPs Defined by Monotone Patterns

    Carbonnel, C., Cohen, D. A., Cooper, M. C. & Živný, S., 20 Feb 2018, 35th Symposium on Theoretical Aspects of Computer Science, STACS 2018. Niedermeier, R. & Vallée, B. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Vol. 96. p. 19:1-19:15 15 p. 19

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  8. Published

    The Expressive Power of Binary Submodular Functions

    Zivný, S., Cohen, D. A. & Jeavons, P. G., 2009, MFCS 2009. p. 744-757

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  9. Chapter › Research
  10. Published

    A Structural Decomposition for Hypergraphs

    Jeavons, P. G., Cohen, D. A. & Gyssens, M., 1994, Jerusalem Combinatorics ’93. Barcelo, H. & Kalai, G. (eds.). American Mathematical Society, p. 161-177 17 p. (Contemporary Mathematics; vol. 178).

    Research output: Chapter in Book/Report/Conference proceedingChapter

  11. Published

    Parameterized Complexity of the Workflow Satisfiability Problem

    Cohen, D., Crampton, J., Gutin, Z. & Wahlstrom, M., 2017, Combinatorial Optimization and Graph Algorithms. Fukunaga, T. & Kawarabayashi, K. (eds.). Springer-Verlag, p. 101-120 20 p.

    Research output: Chapter in Book/Report/Conference proceedingChapter

  12. Published

    The complexity of constraint languages

    Cohen, D. & Jeavons, P., 2006, Handbook of Constraint Programming. Rossi, F., van Beek, P. & Walsh, T. (eds.). Elsevier

    Research output: Chapter in Book/Report/Conference proceedingChapter

  13. Published

    The Expressive Power of Valued Constraints: Hierarchies and Collapses

    Cohen, D., Jeavons, P. & ŽZivný, S., 2007, Principles and Practice of Constraint Programming – CP 2007. Bessière, C. (ed.). Berlin and Heidelberg: Springer, p. 798-805 8 p.

    Research output: Chapter in Book/Report/Conference proceedingChapter

  14. Article › Research › Peer-reviewed
  15. Published

    A maximal tractable class of soft constraints

    Cohen, D., Cooper, M., Jeavons, P. & Krokhin, A., 2004, In: Journal of Artificial Intelligence Research. 22, p. 1-22

    Research output: Contribution to journalArticlepeer-review

  16. Published

    A unified theory of structural tractability for constraint satisfaction problems

    Cohen, D., Jeavons, P. & Gyssens, M., Aug 2008, In: Journal of Computer and System Sciences. 74, 5, p. 721-743 23 p.

    Research output: Contribution to journalArticlepeer-review

  17. Published

    Algorithms for the workflow satisfiability problem engineered for counting constraints

    Cohen, D., Crampton, J., Gagarin, A., Gutin, G. & Jones, M., Jul 2016, In: Journal of Combinatorial Optimization. 32, 1, p. 3–24 22 p.

    Research output: Contribution to journalArticlepeer-review

  18. Published

    An Algebraic Theory of Complexity for Discrete Optimisation

    Cohen, D. A., Cooper, M. C., Creed, P., Jeavons, P. G. & Živný, S., 2013, In: SIAM Journal on Computing. 42, 5, p. 1915-1939 24 p.

    Research output: Contribution to journalArticlepeer-review

  19. E-pub ahead of print

    Binarisation for Valued Constraint Satisfaction Problems

    Cohen, D., Cooper, M., Jeavons, P., Krokhin, A., Powell, R. & Zivny, S., 3 Oct 2017, (E-pub ahead of print) In: SIAM Journal on Discrete Mathematics. 31, 4, p. 2279-2300 22 p.

    Research output: Contribution to journalArticlepeer-review

  20. Published

    Binary constraint satisfaction problems defined by excluded topological minors

    Cohen, D., Cooper, M. C., Jeavons, P. G. & Zivny, S., Feb 2019, In: Infor. and Computation. 264, p. 12-31 20 p.

    Research output: Contribution to journalArticlepeer-review

  21. Published

    Building tractable disjunctive constraints

    Cohen, D. A., Jeavons, P. G., Jonsson, P. & Koubarakis, M., 2000, In: Journal of the ACM. 47, p. 826-853 28 p.

    Research output: Contribution to journalArticlepeer-review

  22. Published

    Characterising Tractable Constraints

    Cooper, M. C., Cohen, D. A. & Jeavons, P. G., 1994, In: Artificial Intelligence. 65, 2, p. 347-361 15 p.

    Research output: Contribution to journalArticlepeer-review

  23. Published

    Closure Properties of Constraints

    Jeavons, P. G., Cohen, D. A. & Gyssens, M., 1997, In: Journal of the ACM. 44, p. 527-548 22 p.

    Research output: Contribution to journalArticlepeer-review

  24. Published

    Constraints and universal algebra

    Jeavons, P. G., Cohen, D. A. & Pearson, J. K., 1998, In: Annals of Mathematics and Artificial Intelligence. 24, p. 51-67 17 p.

    Research output: Contribution to journalArticlepeer-review

  25. Published

    Constraints, Consistency and Closure

    Jeavons, P. G., Cohen, D. A. & Cooper, M., 1998, In: Artificial Intelligence. 101, 1-2, p. 251-265 15 p.

    Research output: Contribution to journalArticlepeer-review

  26. Published

    Decomposing Constraint Satisfaction Problems Using Database Techniques

    Gyssens, M., Jeavons, P. G. & Cohen, D. A., 1994, In: Artificial Intelligence. 66, 1, p. 57-89 33 p.

    Research output: Contribution to journalArticlepeer-review

  27. Published

    Domain permutation reduction for constraint satisfaction problems

    Green, M. J. & Cohen, D. A., May 2008, In: Artificial Intelligence. 172, 8-9, p. 1094-1118 25 p.

    Research output: Contribution to journalArticlepeer-review

  28. Published

    Generalising submodularity and Horn clauses: tractable optimization problems defined by tournament pair multimorphisms

    Cohen, D., Cooper, M. & Jeavons, P., 2008, In: Theoretical Computer Science. 401, 1-3, p. 36-51 16 p.

    Research output: Contribution to journalArticlepeer-review

  29. Published

    How to Determine the Expressive Power of Constraints

    Jeavons, P. G., Cohen, D. A. & Gyssens, M., 1999, In: Constraints. 4, 2, p. 113-131 19 p.

    Research output: Contribution to journalArticlepeer-review