Complexity of hierarchical trees in evidence theory

In this article we propose a structure called hierarchical tree to reduce the complexity of the Dempster's rule of combination in evidence theory. Our algorithm is bounded by O(2²ⁿ⁻²) in the worst case versus O(2²ⁿ) for the brute-force algorithm. We can hope for a better average complexity. Furthermore, we propose algorithms based on hierarchical trees to reduce the complexity of the computation of Bel, Pl and Q functions.