Sites Inria

Version française


International workshop on graphs and constraints

Florent Capelli, member of Links Team will organise an international workshop on August 27th. This workshop on Graphs and Contains is affiliated and co-located with The International Conference on Principles and Practice of Constraint Programming (CP 2018) will take place at Euratechnologies in Lille.

  • Date : 27/08/2018
  • Place : Euratechnologies

Graphs and constraint programming have long been intimately connected in several ways. We only give a non-exhaustive list of such links:

  • Graph algorithms feature prominently in filtering algorithms for global constraints, most prominently the AllDifferent constraint.
  • The variable dependency graph has been used to characterize tractable classes of constraint satisfaction problems.
  • The micro structure graph has been used to define new propagation algorithms and to analyze the strength of existing algorithms.
  • Constraint based techniques have been used to attack Ramsey type problems in combinatorics.
  • Graph isomorphism algorithms are used to automatically detect and exploit symmetries in Boolean satisfiability.

Several of the areas sketched above have made big progress over the last few years. For example, the understanding of the micro structure of CSP instances has been better understood by considering forbidden patterns. Similarly, constraint based techniques for combinatorial problems have shown several conjectures that had been open for a long time. The goal of the International Workshop on Graphs and Constraints is thus to bring together researcher from these and other strains of research to present their work and exchange different perspectives.

The invited speaker is Ciaran McCreesh of the University of Glasgow.

Keywords: IA Graph Artificial Intelligence