Constrained graph problems are about finding graphs respecting a given set of constraints. These problems occur in many areas. For example, security properties, biological reaction mechanisms, ecological predator/prey relationships, compiler code optimizations, and logic circuit fault diagnosis are just a few of the areas in which graph constraints play an important role. This thesis proposes a constraint programming approach for solving these problems. We present new constraints defined on top of the notions of domination and transitive closure, and their search algorithms. We have implemented these constraints in the state-of-the-art Gecode system and shown that they are competitive with or better than other approaches in realistic scenarios. / Les problèmes de graphes contraints concernent la recherche de graphes qui respectent un ensemble donné de contraintes. Ils apparaissent dans de nombreux domaines. Par exemple, la sécurité dans les logiciels, les méchanismes des réactions biologiques, les relations prédateur/proie en écologie, l'optimisation de code par les compilateurs, et le diagnostic de pannes dans des circuits logiques sont quelques-uns des domaines dans lesquels les contraintes de graphes jouent un rôle important. Cette thèse propose une approche basée sur la programmation par contraintes pour résoudre ces problèmes. Nous présentons de nouvelles contraintes définies sur les notions de domination et de clôture transitive, ainsi que leurs algorithmes de recherche. Nous avons implémenté ces contraintes dans le système de pointe Gecode, et avons montré notre approche compétitive et parfois meilleure que d'autres approches dans des cas réalistes.
| Identifer | oai:union.ndltd.org:UCL/oai:ucl.ac.be:ETDUCL:BelnUcetd-11272006-164211 |
| Date | 10 November 2007 |
| Creators | Quesada, Luis |
| Publisher | Universite catholique de Louvain |
| Source Sets | UCL |
| Language | English |
| Detected Language | French |
| Type | text |
| Format | application/pdf |
| Source | http://edoc.bib.ucl.ac.be:81/ETD-db/collection/available/BelnUcetd-11272006-164211/ |
| Rights | unrestricted, J'accepte que le texte de la thèse (ci-après l'oeuvre), sous réserve des parties couvertes par la confidentialité, soit publié dans le recueil électronique des thèses UCL. A cette fin, je donne licence à l'UCL : - le droit de fixer et de reproduire l'oeuvre sur support électronique : logiciel ETD/db - le droit de communiquer l'oeuvre au public Cette licence, gratuite et non exclusive, est valable pour toute la durée de la propriété littéraire et artistique, y compris ses éventuelles prolongations, et pour le monde entier. Je conserve tous les autres droits pour la reproduction et la communication de la thèse, ainsi que le droit de l'utiliser dans de futurs travaux. Je certifie avoir obtenu, conformément à la législation sur le droit d'auteur et aux exigences du droit à l'image, toutes les autorisations nécessaires à la reproduction dans ma thèse d'images, de textes, et/ou de toute oeuvre protégés par le droit d'auteur, et avoir obtenu les autorisations nécessaires à leur communication à des tiers. Au cas où un tiers est titulaire d'un droit de propriété intellectuelle sur tout ou partie de ma thèse, je certifie avoir obtenu son autorisation écrite pour l'exercice des droits mentionnés ci-dessus. |
Page generated in 0.002 seconds