Seminario Interdipartimentale di Algoritmica
 
 
 

Dipartimento di Informatica e Sistemistica, DIS
via Salaria 113, II piano
Aula C2

Abstract:
Constraint Programming (CP) is a rich source of algorihtmic problems. CP is a powerful programming paradigm. Many difficult search problems can be formulated succinctly as constraint programs. CP combines exhaustive search with effective methods for guiding the search and for narrowing the search space. Constraints can be low-level, e.g., the values of two variables must be distinct, or high-level, e.g., the values of a set of n variables must be pairwise distinct (alldiff constraint). It is the narrowing step for high-level constraints where efficient combinatorial algorithms come in. After a gentle introduction into constraint programming I will use the alldiff, the pairing and the sortedness constraints to make the connection with graph algorithms. I will illustrate how known algorithmic knowledge can be applied and how new questions arise. For example, the alldiff constraint is intimately related to perfect matchings in bipartite graphs. The satisfiability problem amounts to the problem of deciding the existence of a perfect matching (= a classical problem) and the narrowing problem amounts to finding all edges that belong to no perfect matching (= a not so classical problem). The pairing constraint corresponds to the perfect matching problem in general graphs. We report about theoretical and experimental results.