A LOWER BOUND OF THE EXPECTED MAXIMUM NUMBER OF VERTEX-DISJOINT s-t PATHS ON PROBABILISTIC GRAPHS

概要

論文の詳細を見る
The problem of computing the expected maximum number Ψ(G,p) of vertex-disjoint s-t paths for a probabilistic graph (G, p) is considered in this paper, where G is a two-terminal graph with specified source vertex s and sink vertex t(s ≠ t) in which each edge has a statistically independent failure probability and each vertex is assumed to be failure-free, and p is a vector of failure probabilities of edges. This computing problem is NP-hard, even though graphs are restricted to several special classes of graphs, e.g., planar graphs, s-t out-in bitrees and s-t complete multi-stage graphs. In this paper, we propose a lower bound Ψ___(G,f,p) of Ψ(G,p) for a probabilistic graph (G,p) based on an s-t path number function f of G. Although the lower bound does not seem to be efficiently computed for a general probabilistic graph, we shall also give a class of probabilistic graphs for which the expected maximum number is efficiently obtained by computing the lower bound.
社団法人日本オペレーションズ・リサーチ学会の論文