Skip to Main content Skip to Navigation
Conference papers

Distributed tree decomposition with privacy

Abstract : 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. 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 (i.e. when used without these two restrictions). Until now, the state of the art in a 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.
Document type :
Conference papers
Complete list of metadata

Cited literature [24 references]  Display  Hide  Download
Contributor : Philippe Dague Connect in order to contact the contributor
Submitted on : Tuesday, February 19, 2013 - 2:24:45 PM
Last modification on : Sunday, June 26, 2022 - 11:58:18 AM
Long-term archiving on: : Monday, May 20, 2013 - 4:02:06 AM


Files produced by the author(s)


  • HAL Id : hal-00790112, version 1



Vincent Armant, Laurent Simon, Philippe Dague. Distributed tree decomposition with privacy. CP - 18th International Conference on Principles and Practice of Constraint Programming, Oct 2012, Québec, Canada. ⟨hal-00790112⟩



Record views


Files downloads