Geodesic
Optimization in Boolean-valued networks
Diskretnaya Matematika, Tome 17 (2005) no. 1, pp. 141-146
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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

[1] Dijkstra E. W., “A note on two problems in connection with graphs”, Numer. Math., 1 (1959), 269–271 | DOI | MR | Zbl

[2] Bogomolov A. M., Salii V. N., Algebraicheskie osnovy teorii diskretnykh sistem, Nauka, Moskva, 1997 | MR | Zbl

[3] Thorup M., “Undirected single-source shortest path with positive integer weights in linear time”, J. ACM, 46 (1999), 362–394 | DOI | MR | Zbl

[4] Salii V. N., “Ob optimalnykh putyakh v bulevoznachnoi seti”, Trudy 3-i Mezhd. algebr. konf. v Ukraine, SDPU, Sumy, 2001, 240–241

[5] Emelichev V. A., Melnikov O. I., Sarvanov V. I., Tyshkevich R. I., Lektsii po teorii grafov, Nauka, Moskva, 1990 | MR | Zbl