COMPUTATIONAL ASPECTS OF THE MOBIUS TRANSFORMATION OF GRAPHS

Every (directed) graph G determines a transformation called the Mobius transformation of-or associated with-the graph G. The paper deals with these (general) Mobius transformations. A special case is the Mobius transformation of the Boolean lattice (p-OMEGA, subset-or-equal-to). That special transformation is of major significance for Dempster-Shafer theory. It is, along with Dempster's rule of combination, at the very heart of Dempster-Shafer theory. However, Dempster's rule of combination and the Mobius transformation of (p-OMEGA, subset-or-equal-to) are also, because of their computational costs, two major obstacles to the use of Dempster-Shafer theory for handling uncertainty in expert systems. Traditionally, the Mobius transformations have been defined and studied in the special case of partial order relations only. The framework adopted in the paper is more general and the author considers general binary relations. From the application point of view, the "fast Mobius transformation algorithms" is presented for computing the Mobius transformation of (p-OMEGA, subset-or-equal-to). These "fast Mobius transformation algorithms" have been discovered independently by some people. It is proven here that they are actually the "best" algorithms among a large class of algorithms. These algorithms have a polynomial runtime whereas the usual algorithms have an exponential runtime. From a theoretical point of view the major point of the paper is the functoriality of the Mobius transformation, which implies that it is recursive. Finally, via the commonality functions, a trivial but useful application is provided: an algorithm for computing Dempster's rule of combination that is much faster than the usual one. The appendices provide a series of related fast algorithms for Dempster-Shafer theory.