Complexity of Hierarchical Trees in Evidence Theory
ORSA Journal on Computing · 1994 · Volume 6 · Issue 1
Abstract
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 2 n −2 ) in the worst case versus O (2 2 n ) 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.
Keywords
analysis of algorithms: study of computational complexity, artificial intelligence: evidence theory and Dempster's rule of combination
Enable JavaScript for citation tools and additional paper interactions.