Please use this identifier to cite or link to this item: doi:10.22028/D291-23766
Title: Constraints and Changes
Author(s): Katriel, Irit
Language: English
Year of Publication: 2005
SWD key words: Technische Informatik
Free key words: Global Cardinality Constraint
directed acyclic graph
DDC notations: 004 Computer science, internet
Publikation type: Dissertation
Abstract: This thesis consists of four technical chapters. The first two chapters deal with filtering algorithms for global constraints. Namley, we show improved algorithms for the well known Global Cardinality Constraint. Then we define a new constraint, UseBy and its special case Same, and show efficient filtering algorithms for both. All of the filtering algorithms follow the same approach: model the constraint as a flow problem. The next two chapters deal with dynamic algoritms. That is, algorithms that maintain information about a directed acyclic graph (DAG) while the graph changes. The third chapter deals with the problem of maintaining the topological order of the nodes of a DAG upon deals with the problem of maintaining the topological order of the nodes of a DAG upon a sequence of edge insertions. The fourth chapter deals with the problem of maintaining the longest paths in a directed acyclic graph upon edge insertions and deletions.
Link to this record: urn:nbn:de:bsz:291-scidok-4593
Advisor: Kurt Mehlhorn
Date of oral examination: 10-Feb-2005
Date of registration: 23-Jun-2005
Faculty: SE - Sonstige Einrichtungen
Department: SE - Sonstige Einrichtungen
Collections:SciDok - Der Wissenschaftsserver der Universität des Saarlandes

Files for this record:
File Description SizeFormat 
Dissertation_571_Katriel_Irit_2005.pdf841,79 kBAdobe PDFView/Open

Items in SciDok are protected by copyright, with all rights reserved, unless otherwise indicated.