A lower bound of the expected maximum number of edge-disjoint s-t paths on probabilistic graphs Original Research Article

For a probabilistic graph (G = (V, E, s, t), p), where G is an undirected graph with specified source vertex s and sink vertex t (s ≠ t) in which each edge has independent failure probability and each vertex is assumed to be failure-free, and p = (p(e1), …, p(e¦E¦)) is a vector consisting of failure probabilities p(ei)ʹs of all edges eiʹs in E, we consider the problem of computing the expected maximum number Γ(G,P) of edge-disjoint s-t paths. It is known that this computing problem is NP-hard even if G is restricted to several classes like planar graphs, s-t out-in bitrees and s-t complete multi-stage graphs. In this paper, for a probabilistic graph (G = (V, E, s, t), p), we propose a lower bound of Γ(G,P) and show the necessary and sufficient conditions by which the lower bound coincides with Γ(G,P). Furthermore, we also give a method of computing the lower bound of Γ(G,P) for a probabilistic graph (G = (V, E, s, t), p).