Please use this identifier to cite or link to this item:
doi:10.22028/D291-23755
Title: | Efficient algorithms for constraint propagation and for processing tree descriptions |
Author(s): | Thiel, Sven |
Language: | English |
Year of Publication: | 2004 |
SWD key words: | CSP |
DDC notations: | 004 Computer science, internet |
Publikation type: | Dissertation |
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. |
Link to this record: | urn:nbn:de:bsz:291-scidok-3226 hdl:20.500.11880/23811 http://dx.doi.org/10.22028/D291-23755 |
Advisor: | Kurt Mehlhorn |
Date of oral examination: | 17-May-2004 |
Date of registration: | 15-Jul-2004 |
Faculty: | SE - Sonstige Einrichtungen |
Department: | SE - Sonstige Einrichtungen |
Collections: | SciDok - Der Wissenschaftsserver der Universität des Saarlandes |
Files for this record:
File | Description | Size | Format | |
---|---|---|---|---|
ThielSven_ProfDrKurtMehlhorn.pdf | 3,06 MB | Adobe PDF | View/Open |
Items in SciDok are protected by copyright, with all rights reserved, unless otherwise indicated.