A New Node-Based Algorithm for Identifying the Complete Minimal Cut Set
The binary-state network, which is fundamental to several modern systems, only operates in two states: operational or inoperable. Network reliability is crucial in its planning, design, and evaluation, with the minimal cut (MC) being a cornerstone for reliability algorithms. A recursive binary-addit...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2024-02-01
|
| Series: | Electronics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2079-9292/13/3/603 |
| _version_ | 1797318884001316864 |
|---|---|
| author | Wei-Chang Yeh Guangyi Yang Chia-Ling Huang |
| author_facet | Wei-Chang Yeh Guangyi Yang Chia-Ling Huang |
| author_sort | Wei-Chang Yeh |
| collection | DOAJ |
| description | The binary-state network, which is fundamental to several modern systems, only operates in two states: operational or inoperable. Network reliability is crucial in its planning, design, and evaluation, with the minimal cut (MC) being a cornerstone for reliability algorithms. A recursive binary-addition-tree algorithm (BAT) excels in its capacity to promptly eliminate infeasible vectors. However, it relies on a depth-first search (DFS), a technique surpassed in efficiency by BAT. To the best of our knowledge, no exploration into a recursive MC-based BAT for MC identification has been undertaken thus far. Therefore, this manuscript introduces the recursive node-based BAT, devised such that the <i>i</i>th iteration of the <i>j</i>th vector mirrors its progenitor vector, barring its <i>i</i>th coordinate valued at one. This BAT method, paired with rules to eliminate infeasible vectors, demonstrates high efficiency in deriving MCs. This is evident in the time complexity analysis and tests on 20 benchmark binary-state networks. A thorough examination of the empirical findings highlights the distinctive features and benefits of the proposed approach. Specifically, the strategic reordering of node numbers, along with the isolated nodes concept, significantly reduces the occurrence of infeasible vectors. Simultaneously, the inclusion of edge nodes expedites the feasibility verification process for vectors. Ultimately, the proposed recursive node-based BAT algorithm framework ensures a more efficient process for generating vectors. |
| first_indexed | 2024-03-08T03:58:51Z |
| format | Article |
| id | doaj.art-a9c06ec2aeec435b8dcb693960576cd1 |
| institution | Directory Open Access Journal |
| issn | 2079-9292 |
| language | English |
| last_indexed | 2024-03-08T03:58:51Z |
| publishDate | 2024-02-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Electronics |
| spelling | doaj.art-a9c06ec2aeec435b8dcb693960576cd12024-02-09T15:10:46ZengMDPI AGElectronics2079-92922024-02-0113360310.3390/electronics13030603A New Node-Based Algorithm for Identifying the Complete Minimal Cut SetWei-Chang Yeh0Guangyi Yang1Chia-Ling Huang2Integration and Collaboration Laboratory, Department of Industrial Engineering and Engineering Management, National Tsing Hua University, Hsinchu 300044, TaiwanInstitute of Technology Management, National Tsing Hua University, Hsinchu 300044, TaiwanDepartment of International Logistics and Transportation Management, Kainan University, Taoyuan 33857, TaiwanThe binary-state network, which is fundamental to several modern systems, only operates in two states: operational or inoperable. Network reliability is crucial in its planning, design, and evaluation, with the minimal cut (MC) being a cornerstone for reliability algorithms. A recursive binary-addition-tree algorithm (BAT) excels in its capacity to promptly eliminate infeasible vectors. However, it relies on a depth-first search (DFS), a technique surpassed in efficiency by BAT. To the best of our knowledge, no exploration into a recursive MC-based BAT for MC identification has been undertaken thus far. Therefore, this manuscript introduces the recursive node-based BAT, devised such that the <i>i</i>th iteration of the <i>j</i>th vector mirrors its progenitor vector, barring its <i>i</i>th coordinate valued at one. This BAT method, paired with rules to eliminate infeasible vectors, demonstrates high efficiency in deriving MCs. This is evident in the time complexity analysis and tests on 20 benchmark binary-state networks. A thorough examination of the empirical findings highlights the distinctive features and benefits of the proposed approach. Specifically, the strategic reordering of node numbers, along with the isolated nodes concept, significantly reduces the occurrence of infeasible vectors. Simultaneously, the inclusion of edge nodes expedites the feasibility verification process for vectors. Ultimately, the proposed recursive node-based BAT algorithm framework ensures a more efficient process for generating vectors.https://www.mdpi.com/2079-9292/13/3/603binary-state networknetwork reliabilityminimal cut (MC)binary-addition-tree algorithm (BAT)recursive method |
| spellingShingle | Wei-Chang Yeh Guangyi Yang Chia-Ling Huang A New Node-Based Algorithm for Identifying the Complete Minimal Cut Set Electronics binary-state network network reliability minimal cut (MC) binary-addition-tree algorithm (BAT) recursive method |
| title | A New Node-Based Algorithm for Identifying the Complete Minimal Cut Set |
| title_full | A New Node-Based Algorithm for Identifying the Complete Minimal Cut Set |
| title_fullStr | A New Node-Based Algorithm for Identifying the Complete Minimal Cut Set |
| title_full_unstemmed | A New Node-Based Algorithm for Identifying the Complete Minimal Cut Set |
| title_short | A New Node-Based Algorithm for Identifying the Complete Minimal Cut Set |
| title_sort | new node based algorithm for identifying the complete minimal cut set |
| topic | binary-state network network reliability minimal cut (MC) binary-addition-tree algorithm (BAT) recursive method |
| url | https://www.mdpi.com/2079-9292/13/3/603 |
| work_keys_str_mv | AT weichangyeh anewnodebasedalgorithmforidentifyingthecompleteminimalcutset AT guangyiyang anewnodebasedalgorithmforidentifyingthecompleteminimalcutset AT chialinghuang anewnodebasedalgorithmforidentifyingthecompleteminimalcutset AT weichangyeh newnodebasedalgorithmforidentifyingthecompleteminimalcutset AT guangyiyang newnodebasedalgorithmforidentifyingthecompleteminimalcutset AT chialinghuang newnodebasedalgorithmforidentifyingthecompleteminimalcutset |