Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen: doi:10.22028/D291-23766
Titel: Constraints and Changes
Verfasser: Katriel, Irit
Sprache: Englisch
Erscheinungsjahr: 2005
SWD-Schlagwörter: Technische Informatik
Algorithmus
Freie Schlagwörter: Global Cardinality Constraint
directed acyclic graph
DAG
DDC-Sachgruppe: 004 Informatik
Dokumentart : Dissertation
Kurzfassung: 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 zu diesem Datensatz: urn:nbn:de:bsz:291-scidok-4593
hdl:20.500.11880/23822
http://dx.doi.org/10.22028/D291-23766
Erstgutachter: Kurt Mehlhorn
Tag der mündlichen Prüfung: 10-Feb-2005
SciDok-Publikation: 23-Jun-2005
Fakultät: Sonstige Einrichtungen
Fachrichtung: SE - Sonstige Einrichtungen
Fakultät / Institution:SE - Sonstige Einrichtungen

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat 
Dissertation_571_Katriel_Irit_2005.pdf841,79 kBAdobe PDFÖffnen/Anzeigen


Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.