Computing K-Terminal Reliability of Circular-Arc Graphs

Chien-Min CHEN; Min-Sheng LIN

doi:10.1587/transinf.2016EDP7221

Computing K-Terminal Reliability of Circular-Arc Graphs

Chien-Min CHEN, Min-Sheng LIN

Full Text Views

0

Share
Cite this

Summary :

Let G be a graph and K be a set of target vertices of G. Assume that all vertices of G, except the vertices in K, may fail with given probabilities. The K-terminal reliability of G is the probability that all vertices in K are mutually connected. This reliability problem is known to be #P-complete for general graphs. This work develops the first polynomial-time algorithm for computing the K-terminal reliability of circular-arc graphs.

Publication: IEICE TRANSACTIONS on Information Vol.E99-D No.12 pp.3047-3052

Publication Date: 2016/12/01

Publicized: 2016/09/06

Online ISSN: 1745-1361

DOI: 10.1587/transinf.2016EDP7221

Type of Manuscript: PAPER

Category: Fundamentals of Information Systems

Authors

Chien-Min CHEN
National Taipei University of Technology
Min-Sheng LIN
National Taipei University of Technology

Keyword

algorithm, reliability, circular-arc graphs, interval graphs

Cite this

Copy

Chien-Min CHEN, Min-Sheng LIN, "Computing K-Terminal Reliability of Circular-Arc Graphs" in IEICE TRANSACTIONS on Information, vol. E99-D, no. 12, pp. 3047-3052, December 2016, doi: 10.1587/transinf.2016EDP7221.
Abstract: Let G be a graph and K be a set of target vertices of G. Assume that all vertices of G, except the vertices in K, may fail with given probabilities. The K-terminal reliability of G is the probability that all vertices in K are mutually connected. This reliability problem is known to be #P-complete for general graphs. This work develops the first polynomial-time algorithm for computing the K-terminal reliability of circular-arc graphs.
URL: https://globals.ieice.org/en_transactions/information/10.1587/transinf.2016EDP7221/_p

Copy

@ARTICLE{e99-d_12_3047,
author={Chien-Min CHEN, Min-Sheng LIN, },
journal={IEICE TRANSACTIONS on Information},
title={Computing K-Terminal Reliability of Circular-Arc Graphs},
year={2016},
volume={E99-D},
number={12},
pages={3047-3052},
abstract={Let G be a graph and K be a set of target vertices of G. Assume that all vertices of G, except the vertices in K, may fail with given probabilities. The K-terminal reliability of G is the probability that all vertices in K are mutually connected. This reliability problem is known to be #P-complete for general graphs. This work develops the first polynomial-time algorithm for computing the K-terminal reliability of circular-arc graphs.},
keywords={},
doi={10.1587/transinf.2016EDP7221},
ISSN={1745-1361},
month={December},}

Copy

TY - JOUR
TI - Computing K-Terminal Reliability of Circular-Arc Graphs
T2 - IEICE TRANSACTIONS on Information
SP - 3047
EP - 3052
AU - Chien-Min CHEN
AU - Min-Sheng LIN
PY - 2016
DO - 10.1587/transinf.2016EDP7221
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E99-D
IS - 12
JA - IEICE TRANSACTIONS on Information
Y1 - December 2016
AB - Let G be a graph and K be a set of target vertices of G. Assume that all vertices of G, except the vertices in K, may fail with given probabilities. The K-terminal reliability of G is the probability that all vertices in K are mutually connected. This reliability problem is known to be #P-complete for general graphs. This work develops the first polynomial-time algorithm for computing the K-terminal reliability of circular-arc graphs.
ER -