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

Peng CHENG; Shigeru MASUYAMA

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

Peng CHENG, Shigeru MASUYAMA

Full Text Views

0

Cite this

Summary :

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.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E76-A No.12 pp.2089-2094

Publication Date: 1993/12/25

Publicized

Online ISSN

DOI

Type of Manuscript: PAPER

Category: Graphs, Networks and Matroids

Cite this

Copy

Peng CHENG, Shigeru MASUYAMA, "Computing the Expected Maximum Number of Vertex-Disjoint s-t Paths in a Probabilistic Basically Series-Parallel Digraph" in IEICE TRANSACTIONS on Fundamentals, vol. E76-A, no. 12, pp. 2089-2094, December 1993, doi: .
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e76-a_12_2089/_p

Copy

@ARTICLE{e76-a_12_2089,
author={Peng CHENG, Shigeru MASUYAMA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Computing the Expected Maximum Number of Vertex-Disjoint s-t Paths in a Probabilistic Basically Series-Parallel Digraph},
year={1993},
volume={E76-A},
number={12},
pages={2089-2094},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={December},}

Copy

TY - JOUR
TI - Computing the Expected Maximum Number of Vertex-Disjoint s-t Paths in a Probabilistic Basically Series-Parallel Digraph
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2089
EP - 2094
AU - Peng CHENG
AU - Shigeru MASUYAMA
PY - 1993
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E76-A
IS - 12
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - December 1993
AB - 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.
ER -