Computational Aspects of the Mobius Transform
  In this paper we associate with every (directed) graph G a transformation
called the Mobius transformation of the graph G. The Mobius transformation of
the graph (O) is of major significance for Dempster-Shafer theory of evidence.
However, because it is computationally very heavy, the Mobius transformation
together with Dempster's rule of combination is a major obstacle to the use of
Dempster-Shafer theory for handling uncertainty in expert systems. The major
contribution of this paper is the discovery of the 'fast Mobius
transformations' of (O). These 'fast Mobius transformations' are the fastest
algorithms for computing the Mobius transformation of (O). As an easy but
useful application, we provide, via the commonality function, an algorithm for
computing Dempster's rule of combination which is much faster than the usual
one.
