This dissertation is dedicated to the design and analysis of algorithms for global constraints. Global constraints are one of the major contributors to the success of modern constraint solvers in solving combinatorial and industrial problems. They serve as natural building blocks in the modelling stage providing the user with a rich declarative language for problem specification. Global constraints can also lead to dramatic reduction of the search space during problem solving because their propagation algorithms leverage global knowledge about the problem.

In this work we study a number of useful global constraints, including SEQUENCE, ALL-DIFFERENT , GCC, GRAMMAR and NVALUE. We propose reformulations of these constraints into logically equivalent problems on graphs or into logically equivalent sets of primitive constraints. We analyse existing filtering algorithms for these constraints and prove that our reformulations can simulate filtering algorithms for all these constraints with a slight complexity overhead in some cases. These reformulations have a number of ad- vantages; in particular, they allow adding global constraints to a constraint solver with- out implementing special-purpose filtering algorithms, they guarantee maintaining standard consistency levels for propagation, and their time complexity is similar to or the same as the best known special-purpose filtering algorithms. Finally, we investigate limitations of our approach and show that for some constraints and their filtering algorithms a polynomial size reformulation is not possible.