The Evaluations on Lower Bounds of All-Terminal Reliability by Arc-Packings for General Networks

Takeshi KOIDE; Shuichi SHINMORI; Hiroaki ISHII

The Evaluations on Lower Bounds of All-Terminal Reliability by Arc-Packings for General Networks

Takeshi KOIDE, Shuichi SHINMORI, Hiroaki ISHII

Full Text Views

0

Cite this

Summary :

All-terminal reliability is one of the measurements to evaluate the reliability for network systems. Since it may need exponential time of the network size to compute the exact value of all-terminal reliability, it is important to calculate its tight approximate value, especially its lower bound, at a moderate calculation time. Ramanathan and Colbourn have proposed approaches for lower bounds of all-terminal reliability by using arc-packings but their approaches are not detailed enough to construct concrete algorithms and they have just evaluated their approaches for a particular network. In this paper, we construct concrete algorithms based on their approaches and suggest new algorithms. We also execute computational experiments for general networks in order to evaluate the lower bounds by the algorithms and show the effectiveness of our new algorithms.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E82-A No.5 pp.784-791

Publication Date: 1999/05/25

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

Category

Cite this

Copy

Takeshi KOIDE, Shuichi SHINMORI, Hiroaki ISHII, "The Evaluations on Lower Bounds of All-Terminal Reliability by Arc-Packings for General Networks" in IEICE TRANSACTIONS on Fundamentals, vol. E82-A, no. 5, pp. 784-791, May 1999, doi: .
Abstract: All-terminal reliability is one of the measurements to evaluate the reliability for network systems. Since it may need exponential time of the network size to compute the exact value of all-terminal reliability, it is important to calculate its tight approximate value, especially its lower bound, at a moderate calculation time. Ramanathan and Colbourn have proposed approaches for lower bounds of all-terminal reliability by using arc-packings but their approaches are not detailed enough to construct concrete algorithms and they have just evaluated their approaches for a particular network. In this paper, we construct concrete algorithms based on their approaches and suggest new algorithms. We also execute computational experiments for general networks in order to evaluate the lower bounds by the algorithms and show the effectiveness of our new algorithms.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e82-a_5_784/_p

Copy

@ARTICLE{e82-a_5_784,
author={Takeshi KOIDE, Shuichi SHINMORI, Hiroaki ISHII, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={The Evaluations on Lower Bounds of All-Terminal Reliability by Arc-Packings for General Networks},
year={1999},
volume={E82-A},
number={5},
pages={784-791},
abstract={All-terminal reliability is one of the measurements to evaluate the reliability for network systems. Since it may need exponential time of the network size to compute the exact value of all-terminal reliability, it is important to calculate its tight approximate value, especially its lower bound, at a moderate calculation time. Ramanathan and Colbourn have proposed approaches for lower bounds of all-terminal reliability by using arc-packings but their approaches are not detailed enough to construct concrete algorithms and they have just evaluated their approaches for a particular network. In this paper, we construct concrete algorithms based on their approaches and suggest new algorithms. We also execute computational experiments for general networks in order to evaluate the lower bounds by the algorithms and show the effectiveness of our new algorithms.},
keywords={},
doi={},
ISSN={},
month={May},}

Copy

TY - JOUR
TI - The Evaluations on Lower Bounds of All-Terminal Reliability by Arc-Packings for General Networks
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 784
EP - 791
AU - Takeshi KOIDE
AU - Shuichi SHINMORI
AU - Hiroaki ISHII
PY - 1999
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E82-A
IS - 5
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - May 1999
AB - All-terminal reliability is one of the measurements to evaluate the reliability for network systems. Since it may need exponential time of the network size to compute the exact value of all-terminal reliability, it is important to calculate its tight approximate value, especially its lower bound, at a moderate calculation time. Ramanathan and Colbourn have proposed approaches for lower bounds of all-terminal reliability by using arc-packings but their approaches are not detailed enough to construct concrete algorithms and they have just evaluated their approaches for a particular network. In this paper, we construct concrete algorithms based on their approaches and suggest new algorithms. We also execute computational experiments for general networks in order to evaluate the lower bounds by the algorithms and show the effectiveness of our new algorithms.
ER -