Diskretnaya Matematika, Tome 17 (2005) no. 1, pp. 141-146
Citer cet article
V. N. Salii. Optimization in Boolean-valued networks. Diskretnaya Matematika, Tome 17 (2005) no. 1, pp. 141-146. http://geodesic.mathdoc.fr/item/DM_2005_17_1_a10/
@article{DM_2005_17_1_a10,
author = {V. N. Salii},
title = {Optimization in {Boolean-valued} networks},
journal = {Diskretnaya Matematika},
pages = {141--146},
year = {2005},
volume = {17},
number = {1},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/DM_2005_17_1_a10/}
}
TY - JOUR
AU - V. N. Salii
TI - Optimization in Boolean-valued networks
JO - Diskretnaya Matematika
PY - 2005
SP - 141
EP - 146
VL - 17
IS - 1
UR - http://geodesic.mathdoc.fr/item/DM_2005_17_1_a10/
LA - ru
ID - DM_2005_17_1_a10
ER -
%0 Journal Article
%A V. N. Salii
%T Optimization in Boolean-valued networks
%J Diskretnaya Matematika
%D 2005
%P 141-146
%V 17
%N 1
%U http://geodesic.mathdoc.fr/item/DM_2005_17_1_a10/
%G ru
%F DM_2005_17_1_a10
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)$.
