Abstract:
By a Boolean-valued network, or a $B$-network, is meant a directed multigraph whose each
arc is labelled with some element of a fixed finite Boolean algebra $B$.
The union of all labels along a given path is called the valuation
of the path and the number of atoms of the Boolean algebra $B$ contained in the
valuation is called the variety of the path. An $(s,t)$-path, a path from
an initial vertex
$s$ to a prescribed vertex $t$, is called optimal if it has the minimum
variety possible for $(s,t)$-paths and among the $(s,t)$-paths of such variety
has the minimum length (the minimum number of arcs). In this study,
we suggest an algorithm which finds one of the optimal $(s,t)$-paths in a $B$-network
with $n$ vertices at time $O(n^3)$.