IEICE TRANSACTIONS on Information
Computing K-Terminal Reliability of Circular-Arc Graphs
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
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
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://global.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 -
English
