This thesis consists of two parts. In the first part we present propagation algorithms, which are used for solving constraint satisfaction problems (CSP). One approach to solve a CSP is based on interleaving constraint propagation and search. The task of a propagation algorithm is to prune portions of the search space which do not contain a solution so that the search does not have to explore them. We present propagation algorithms for the following constraints: Sortedness, Alldiff, WeightedPartialAlldiff and NonOverlapping (of convex polygons).
The second part deals with a tree processing problem, which is represented as a dominance graph. The task is to assemble a collection of tree fragments into a tree T such that the ancestor relation of T satisfies some given constraints. We discuss efficient algorithms for deciding whether a dominance graph D has a solved form and for enumerating all (minimal) solved forms of D.