Solving constrained graph problems using reachability constraints based on transitive closure and dominators / Résolution de problèmes de graphes contraints à l'aide de contraintes d'atteignabilité basées sur la clôture transitive et les dominateurs

Quesada, Luis
(2007)

Files

thesis.pdf
  • Open Access
  • Adobe PDF
  • 1.43 MB
Download

Details

Authors
  • Quesada, LuisUCLouvain
    author
Supervisors
Van Roy, Peter
Abstract
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.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Quesada, L. (2007). Solving constrained graph problems using reachability constraints based on transitive closure and dominators / Résolution de problèmes de graphes contraints à l’aide de contraintes d’atteignabilité basées sur la clôture transitive et les dominateurs. https://hdl.handle.net/2078.5/129421