IDEAS home Printed from https://ideas.repec.org/a/eee/reensy/v252y2024ics0951832024005428.html
   My bibliography  Save this article

A novel scanline algorithm for generating ordered variables

Author

Listed:
  • Wu, Baichao

Abstract

Rapid and timely network reliability assessment is one of the effective means for the reliable operation of infrastructure systems or other systems. Previous studies have found that binary decision diagram (BDD) -based network reliability algorithms are more efficient than other algorithms due to their advantage of avoiding repeated computation. The computational complexity of the BDD-based network reliability algorithm depends heavily on the maximum number of partitions in the network decomposition, notated as Fmax; the higher the Fmax is, the lower the computational efficiency is, and vice versa. However, previous studies did not consider the Fmax in generating ordered variables by depth-first search (DFS), breadth-first search (BFS) or network-driven search (NDS) algorithms, therefore, the efficiency of the network decomposition is largely a matter of luck by the previous algorithms. In this paper, a novel scanline algorithm was proposed aiming to obtain ordered variables with as small Fmax as possible. Experiments on the selected networks results show that the Fmax of the ordered variables generated by the proposed algorithm is smaller and more robust than that of the previous algorithms or their improved versions.

Suggested Citation

  • Wu, Baichao, 2024. "A novel scanline algorithm for generating ordered variables," Reliability Engineering and System Safety, Elsevier, vol. 252(C).
    • Handle: RePEc:eee:reensy:v:252:y:2024:i:c:s0951832024005428
    DOI: 10.1016/j.ress.2024.110470
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0951832024005428
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ress.2024.110470?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Yeh, Wei-Chang & Tan, Shi-Yi & Zhu, Wenbo & Huang, Chia-Ling & Yang, Guang-yi, 2022. "Novel binary addition tree algorithm (BAT) for calculating the direct lower-bound of the highly reliable binary-state network reliability," Reliability Engineering and System Safety, Elsevier, vol. 223(C).
    2. Sebastio, Stefano & Trivedi, Kishor S. & Wang, Dazhi & Yin, Xiaoyan, 2014. "Fast computation of bounds for two-terminal network reliability," European Journal of Operational Research, Elsevier, vol. 238(3), pages 810-823.
    3. Kawahara, Jun & Sonoda, Koki & Inoue, Takeru & Kasahara, Shoji, 2019. "Efficient construction of binary decision diagrams for network reliability with imperfect vertices," Reliability Engineering and System Safety, Elsevier, vol. 188(C), pages 142-154.
    4. Yeh, Wei-Chang, 2021. "Novel binary-addition tree algorithm (BAT) for binary-state network reliability problem," Reliability Engineering and System Safety, Elsevier, vol. 208(C).
    5. Yeh, Wei-Chang, 2021. "A quick BAT for evaluating the reliability of binary-state networks," Reliability Engineering and System Safety, Elsevier, vol. 216(C).
    6. Liu, Tao & Bai, Guanghan & Tao, Junyong & Zhang, Yun-An & Fang, Yining & Xu, Bei, 2022. "Modeling and evaluation method for resilience analysis of multi-state networks," Reliability Engineering and System Safety, Elsevier, vol. 226(C).
    7. Yeh, Wei-Chang, 2023. "QB-II for evaluating the reliability of binary-state networks," Reliability Engineering and System Safety, Elsevier, vol. 230(C).
    8. Yeh, Wei-Chang, 2023. "Novel recursive inclusion-exclusion technology based on BAT and MPs for heterogeneous-arc binary-state network reliability problems," Reliability Engineering and System Safety, Elsevier, vol. 231(C).
    9. Yeh, Wei-Chang & Chu, Ta-Chung, 2018. "A novel multi-distribution multi-state flow network and its reliability optimization problem," Reliability Engineering and System Safety, Elsevier, vol. 176(C), pages 209-217.
    10. Wu, Baichao & Tang, Aiping & Wu, Jie, 2016. "Modeling cascading failures in interdependent infrastructures under terrorist attacks," Reliability Engineering and System Safety, Elsevier, vol. 147(C), pages 1-8.
    11. Yeh, Wei-Chang, 2024. "A new hybrid inequality BAT for comprehensive all-level d-MP identification using minimal paths in Multistate Flow Network reliability analysis," Reliability Engineering and System Safety, Elsevier, vol. 244(C).
    12. Reed, Sean & Löfstrand, Magnus & Andrews, John, 2019. "An efficient algorithm for computing exact system and survival signatures of K-terminal network reliability," Reliability Engineering and System Safety, Elsevier, vol. 185(C), pages 429-439.
    13. Wu, Baichao & Sun, Long, 2024. "A novel layer-by-layer recursive decomposition algorithm for calculation of network reliability," Reliability Engineering and System Safety, Elsevier, vol. 244(C).
    14. Yeh, Wei-Chang & Hao, Zhifeng & Forghani-elahabad, Majid & Wang, Gai-Ge & Lin, Yih-Lon, 2021. "Novel Binary-Addition Tree Algorithm for Reliability Evaluation of Acyclic Multistate Information Networks," Reliability Engineering and System Safety, Elsevier, vol. 210(C).
    15. Mo, Yuchang & Xing, Liudong & Zhong, Farong & Pan, Zhusheng & Chen, Zhongyu, 2014. "Choosing a heuristic and root node for edge ordering in BDD-based network reliability analysis," Reliability Engineering and System Safety, Elsevier, vol. 131(C), pages 83-93.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Wu, Baichao & Sun, Long, 2024. "A novel layer-by-layer recursive decomposition algorithm for calculation of network reliability," Reliability Engineering and System Safety, Elsevier, vol. 244(C).
    2. Cui, Hongjun & Wang, Fei & Ma, Xinwei & Zhu, Minqing, 2022. "A novel fixed-node unconnected subgraph method for calculating the reliability of binary-state networks," Reliability Engineering and System Safety, Elsevier, vol. 226(C).
    3. Yeh, Wei-Chang, 2024. "Time-reliability optimization for the stochastic traveling salesman problem," Reliability Engineering and System Safety, Elsevier, vol. 248(C).
    4. Yeh, Wei-Chang, 2022. "Novel direct algorithm for computing simultaneous all-level reliability of multistate flow networks," Reliability Engineering and System Safety, Elsevier, vol. 225(C).
    5. Yeh, Wei-Chang & Du, Chia-Ming & Tan, Shi-Yi & Forghani-elahabad, Majid, 2023. "Application of LSTM based on the BAT-MCS for binary-state network approximated time-dependent reliability problems," Reliability Engineering and System Safety, Elsevier, vol. 235(C).
    6. Yeh, Wei-Chang, 2024. "A new hybrid inequality BAT for comprehensive all-level d-MP identification using minimal paths in Multistate Flow Network reliability analysis," Reliability Engineering and System Safety, Elsevier, vol. 244(C).
    7. Niu, Yi-Feng & Xiang, Hai-Yan & Xu, Xiu-Zhen, 2024. "Expected performance evaluation and optimization of a multi-distribution multi-state logistics network based on network reliability," Reliability Engineering and System Safety, Elsevier, vol. 251(C).
    8. Yeh, Wei-Chang & Tan, Shi-Yi & Zhu, Wenbo & Huang, Chia-Ling & Yang, Guang-yi, 2022. "Novel binary addition tree algorithm (BAT) for calculating the direct lower-bound of the highly reliable binary-state network reliability," Reliability Engineering and System Safety, Elsevier, vol. 223(C).
    9. Davila-Frias, Alex & Yodo, Nita & Le, Trung & Yadav, Om Prakash, 2023. "A deep neural network and Bayesian method based framework for all-terminal network reliability estimation considering degradation," Reliability Engineering and System Safety, Elsevier, vol. 229(C).
    10. Yeh, Wei-Chang & Zhu, Wenbo & Tan, Shi-Yi & Wang, Gai-Ge & Yeh, Yuan-Hui, 2022. "Novel general active reliability redundancy allocation problems and algorithm," Reliability Engineering and System Safety, Elsevier, vol. 218(PA).
    11. Yeh, Wei-Chang, 2022. "Novel self-adaptive Monte Carlo simulation based on binary-addition-tree algorithm for binary-state network reliability approximation," Reliability Engineering and System Safety, Elsevier, vol. 228(C).
    12. Hao, Zhifeng & Yeh, Wei-Chang & Tan, Shi-Yi, 2021. "One-batch preempt deterioration-effect multi-state multi-rework network reliability problem and algorithms," Reliability Engineering and System Safety, Elsevier, vol. 215(C).
    13. Monfared, M.A.S. & Rezazadeh, Masoumeh & Alipour, Zohreh, 2022. "Road networks reliability estimations and optimizations: A Bi-directional bottom-up, top-down approach," Reliability Engineering and System Safety, Elsevier, vol. 222(C).
    14. Yeh, Wei-Chang & Tan, Shi-Yi & Forghani-elahabad, Majid & Khadiri, Mohamed El & Jiang, Yunzhi & Lin, Chen-Shiun, 2022. "New binary-addition tree algorithm for the all-multiterminal binary-state network reliability problem," Reliability Engineering and System Safety, Elsevier, vol. 224(C).
    15. Chen, Liwei & Cheng, Chunchun & Dui, Hongyan & Xing, Liudong, 2022. "Maintenance cost-based importance analysis under different maintenance strategies," Reliability Engineering and System Safety, Elsevier, vol. 222(C).
    16. Yeh, Wei-Chang, 2021. "Novel Algorithm for Computing All-Pairs Homogeneity-Arc Binary-State Undirected Network Reliability," Reliability Engineering and System Safety, Elsevier, vol. 216(C).
    17. Vaibhav Gaur & Om Prakash Yadav & Gunjan Soni & Ajay Pal Singh Rathore, 2021. "A literature review on network reliability analysis and its engineering applications," Journal of Risk and Reliability, , vol. 235(2), pages 167-181, April.
    18. Niu, Yi-Feng & Zhou, Run-Hui & Xu, Xiu-Zhen & Xiang, Hai-Yan, 2024. "A reliability index to measure multi-state flow network considering capacity restoration level and maintenance cost," Reliability Engineering and System Safety, Elsevier, vol. 250(C).
    19. Huang, Ding-Hsiang & Huang, Cheng-Fu & Lin, Yi-Kuei, 2020. "A novel minimal cut-based algorithm to find all minimal capacity vectors for multi-state flow networks," European Journal of Operational Research, Elsevier, vol. 282(3), pages 1107-1114.
    20. Chen, Shun & Zhao, Xudong & Chen, Zhilong & Hou, Benwei & Wu, Yipeng, 2022. "A game-theoretic method to optimize allocation of defensive resource to protect urban water treatment plants against physical attacks," International Journal of Critical Infrastructure Protection, Elsevier, vol. 36(C).

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:reensy:v:252:y:2024:i:c:s0951832024005428. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: https://www.journals.elsevier.com/reliability-engineering-and-system-safety .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.