Optimization in Boolean-valued networks

V. N. Salii

Diskretnaya Matematika, Tome 17 (2005) no. 1, pp. 141-146

Résumé

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)$.