Publication details

Saarland University Computer Science

Efficient Algorithms for Constraint Propagation and for Processing Tree Descriptions

Sven Thiel

Dissertation, Universitšt des Saarlandes, 2004

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.

Download PDF        Show BibTeX               


Login to edit


Webmaster, Wed Sep 16 10:47:00 2009