Evaluating communication-network reliability with heterogeneous link-capacities using subset enumeration
This paper proposes an improved algorithm to compute the reliability of a communication-network having heterogeneous link capacities. The reliability measure, capacity related reliability (CRR), is a generalization of a two-terminal reliability. A subset-cut-technique (SCT [7]) obtains CRR in two st...
| Main Authors: | , , |
|---|---|
| Format: | Journal Article |
| Published: |
RAMS Consultants
2006
|
| Online Access: | http://hdl.handle.net/20.500.11937/33784 |
| _version_ | 1848754042848673792 |
|---|---|
| author | Soh, Sieteng Lim, Kok Rai, S. |
| author_facet | Soh, Sieteng Lim, Kok Rai, S. |
| author_sort | Soh, Sieteng |
| building | Curtin Institutional Repository |
| collection | Online Access |
| description | This paper proposes an improved algorithm to compute the reliability of a communication-network having heterogeneous link capacities. The reliability measure, capacity related reliability (CRR), is a generalization of a two-terminal reliability. A subset-cut-technique (SCT [7]) obtains CRR in two steps. First, SCT generates non-redundant subset-cut (SC) of the evaluated network. Second, the technique uses a sum-of-disjoint product algorithm to compute CRR from the generated SC. The computational complexity of SCT depends on the total number of subsets generated, the total number of internal (external) redundant SC generated and removed, and the total number of cuts in the network that are used to generate SC. The SCT generates too many subsets and internal (external)-redundant SC. In this paper, we propose a new subset cut enumeration (SCE) technique, which significantly reduces the total number of enumerated subsets and the total number of internal-redundant SC. Hence, the non-redundant SC are generated more efficiently. Examples are given to illustrate the technique, and the time complexity of our SCE is also described. Our method has been implemented in C and results show that SCE performs better than SCT. |
| first_indexed | 2025-11-14T08:34:07Z |
| format | Journal Article |
| id | curtin-20.500.11937-33784 |
| institution | Curtin University Malaysia |
| institution_category | Local University |
| last_indexed | 2025-11-14T08:34:07Z |
| publishDate | 2006 |
| publisher | RAMS Consultants |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | curtin-20.500.11937-337842017-01-30T13:39:24Z Evaluating communication-network reliability with heterogeneous link-capacities using subset enumeration Soh, Sieteng Lim, Kok Rai, S. This paper proposes an improved algorithm to compute the reliability of a communication-network having heterogeneous link capacities. The reliability measure, capacity related reliability (CRR), is a generalization of a two-terminal reliability. A subset-cut-technique (SCT [7]) obtains CRR in two steps. First, SCT generates non-redundant subset-cut (SC) of the evaluated network. Second, the technique uses a sum-of-disjoint product algorithm to compute CRR from the generated SC. The computational complexity of SCT depends on the total number of subsets generated, the total number of internal (external) redundant SC generated and removed, and the total number of cuts in the network that are used to generate SC. The SCT generates too many subsets and internal (external)-redundant SC. In this paper, we propose a new subset cut enumeration (SCE) technique, which significantly reduces the total number of enumerated subsets and the total number of internal-redundant SC. Hence, the non-redundant SC are generated more efficiently. Examples are given to illustrate the technique, and the time complexity of our SCE is also described. Our method has been implemented in C and results show that SCE performs better than SCT. 2006 Journal Article http://hdl.handle.net/20.500.11937/33784 RAMS Consultants restricted |
| spellingShingle | Soh, Sieteng Lim, Kok Rai, S. Evaluating communication-network reliability with heterogeneous link-capacities using subset enumeration |
| title | Evaluating communication-network reliability with heterogeneous link-capacities using subset enumeration |
| title_full | Evaluating communication-network reliability with heterogeneous link-capacities using subset enumeration |
| title_fullStr | Evaluating communication-network reliability with heterogeneous link-capacities using subset enumeration |
| title_full_unstemmed | Evaluating communication-network reliability with heterogeneous link-capacities using subset enumeration |
| title_short | Evaluating communication-network reliability with heterogeneous link-capacities using subset enumeration |
| title_sort | evaluating communication-network reliability with heterogeneous link-capacities using subset enumeration |
| url | http://hdl.handle.net/20.500.11937/33784 |