  For the case of evidence ordered in a complete directed acyclic graph this
paper presents a new algorithm with lower computational complexity for
Dempster's rule than that of step-by-step application of Dempster's rule. In
this problem, every original pair of evidences, has a corresponding evidence
against the simultaneous belief in both propositions. In this case, it is
uncertain whether the propositions of any two evidences are in logical
conflict. The original evidences are associated with the vertices and the
additional evidences are associated with the edges. The original evidences are
ordered, i.e., for every pair of evidences it is determinable which of the two
evidences is the earlier one. We are interested in finding the most probable
completely specified path through the graph, where transitions are possible
only from lower- to higher-ranked vertices. The path is here a representation
for a sequence of states, for instance a sequence of snapshots of a physical
object's track. A completely specified path means that the path includes no
other vertices than those stated in the path representation, as opposed to an
incompletely specified path that may also include other vertices than those
stated. In a hierarchical network of all subsets of the frame, i.e., of all
incompletely specified paths, the original and additional evidences support
subsets that are not disjoint, thus it is not possible to prune the network to
a tree. Instead of propagating belief, the new algorithm reasons about the
logical conditions of a completely specified path through the graph. The new
algorithm is O(|THETA| log |THETA|), compared to O(|THETA| ** log |THETA|) of
the classic brute force algorithm.
