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.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.