Tree Decomposition of Graphical Models is a well known method for mapping a graph into a tree, that is commonly used to speed up solving many problems in Graph theory, Constraints optimization, Planning, Databases, Knowledge Representation, ...
However, in a distributed case, one may have to respect the privacy rules (a subset of variables may have to be kept secret in a peer), and the initial network architecture (no link can be dynamically added). In this context, we propose a new distributed method, based on token passing and local elections, that shows performances (in the jointree quality) close to the state of the art Bucket Elimination in a centralized case ie when used without these two restrictions). Until now, the state of the art in distributed context was using a Depth-First traversal with a clever heuristic. It is outperformed by our method on two families of problems sharing the small-world property.



Activités de recherche
  ° Compilation de bases de connaissances
  ° Algorithmique répartie
  ° Optimisation
  ° Algorithmique de graphes
  ° Pair à Pair

Equipe
  ° Intelligence Artificielle et Systèmes d'Inférence

Contact
  [aucun]