Efficient algorithms for constraint propagation and for processing tree descriptions

Abstract

This thesis consists of two parts. In the first part we present propagation algorithms, which to solve a CSP is based on interleaving constraint progagation and search. The task of a propagation alogrithm 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 alogrithms for the following constraints: Sortedness, Alldiff, WeightedPartialAlldiff and NonOverlapping (of two 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.

Diese Arbeit besteht aus zwei Teilen. Im ersten Teil behandeln wir Propagierungsalgorithmen zum Lösen von Constraint-Problemen. Ein Lösungsansatz basiert darauf, Constraint-Propagierung und Suche abzuwechseln. Durch die Propagierung werden Teile des Suchraums eliminiert, die keine Lösung enthalten. Dadurch verringert sich der Raum, der von der Suche exploriert werden muss, und die Lösung(en)werden oftmals schneller gefunden als durch Suche alleine. Wir beschreiben Propagierungsalgorithmen für folgende Constraints: Sortedness, Alldiff, WeightedPartial Alldiff und NonOverlapping. Der zweite Teil behandelt ein Baumverarbeitungsproblem, das durch einen Dominanzgraphen beschrieben wird. Das Problem besteht darin, Baumfragmente so zu einem Baum zusammen zu setzen, dass bestimmte Anforderungen an die Vorfahr-Relation des Baumes erfüllt sind. Wir entwickeln einen Linearzeit Lösbarkeitstest und effiziente Algorithmen zum Aufzählen aller (minimalen) gelösten Formen eines Dominanzgraphen.