V. N. Salii
Optimisation in Boolean-valued networks
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).
Discrete Mathematics and Applications, Walter de Gruyter
Print ISSN: 0924-9266
Volume: 15, 04/2005
Pages: 195 - 200
Show full article (external site)
Show all available items of this journal
Search
