Computing the Expected Maximum Number of Vertex-Disjoint s-t Paths in a Probabilistic Basically Series-Parallel Digraph

Peng CHENG  Shigeru MASUYAMA  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E76-A   No.12   pp.2089-2094
Publication Date: 1993/12/25
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Graphs, Networks and Matroids
probabilistic graph,  expected maximum number of vertex-disjoint s-t paths,  series-parallel undirected graph,  basically series-parallel directed graph,  polynomial time algorithm,  

Full Text: PDF(465.6KB)>>
Buy this Article

In this paper, we propose a polynomial time algorithm for computing the expected maximum number of vertex-disjoint s-t paths in a probabilistic basically series-parallel directed graph and a probabilistic series-parallel undirected graph with distinguished source s and sink t(st), where each edge has a mutually independent failure probability and each vertex is assumed to be failure-free.