IDEAS home Printed from https://ideas.repec.org/a/eee/reensy/v270y2026ics0951832025013201.html

Computing the reliability of hammock networks in quadratic time with respect to length

Author

Listed:
  • Jianu, Mihail
  • Jianu, Marilena
  • DăuÅŸ, Leonard
  • Beiu, Valeriu

Abstract

The paper introduces an efficient algorithm for computing the reliability polynomial of hammock networks. A hammock network of length l and width w is made up of w × l identical devices that independently work with probability p (and fail with probability 1−p). A brute-force algorithm to compute its reliability polynomial would require a running time exponential in w × l. We introduce a new algorithm and prove that it is exponential in w (as expected), while being only quadratic in l. This allows us to compute, for the first time ever, the reliability polynomials of hammock networks of dimensions significantly larger than 8 (the largest reported in the literature).

Suggested Citation

  • Jianu, Mihail & Jianu, Marilena & DăuÅŸ, Leonard & Beiu, Valeriu, 2026. "Computing the reliability of hammock networks in quadratic time with respect to length," Reliability Engineering and System Safety, Elsevier, vol. 270(C).
    • Handle: RePEc:eee:reensy:v:270:y:2026:i:c:s0951832025013201
    DOI: 10.1016/j.ress.2025.112121
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0951832025013201
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ress.2025.112121?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

    for a different version of it.

    References listed on IDEAS

    as
    1. 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.
    2. Frank Arute & Kunal Arya & Ryan Babbush & Dave Bacon & Joseph C. Bardin & Rami Barends & Rupak Biswas & Sergio Boixo & Fernando G. S. L. Brandao & David A. Buell & Brian Burkett & Yu Chen & Zijun Chen, 2019. "Quantum supremacy using a programmable superconducting processor," Nature, Nature, vol. 574(7779), pages 505-510, October.
    3. Goharshady, Amir Kafshdar & Mohammadi, Fatemeh, 2020. "An efficient algorithm for computing network reliability in small treewidth," Reliability Engineering and System Safety, Elsevier, vol. 193(C).
    4. Wu, Baichao, 2025. "A novel d-flow network decomposition algorithm for fast search and efficient storage of all d-MPs," Reliability Engineering and System Safety, Elsevier, vol. 262(C).
    5. 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.
    6. Google Quantum AI and Collaborators, 2025. "Quantum error correction below the surface code threshold," Nature, Nature, vol. 638(8052), pages 920-926, February.
    7. J. Scott Provan & Michael O. Ball, 1984. "Computing Network Reliability in Time Polynomial in the Number of Cuts," Operations Research, INFORMS, vol. 32(3), pages 516-526, June.
    8. 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).
    9. Lins, Isis Didier & Araújo, Lavínia Maria Mendes & Maior, Caio Bezerra Souto & Teixeira, Erico Souza & Bezerra, Pâmela Thays Lins & Moura, Márcio José das Chagas & Droguett, Enrique López, 2025. "Quantum-based optimization methods for the linear redundancy allocation problem: A comparative analysis," Reliability Engineering and System Safety, Elsevier, vol. 262(C).
    10. H. Aghaee Rad & T. Ainsworth & R. N. Alexander & B. Altieri & M. F. Askarani & R. Baby & L. Banchi & B. Q. Baragiola & J. E. Bourassa & R. S. Chadwick & I. Charania & H. Chen & M. J. Collins & P. Cont, 2025. "Scaling and networking a modular photonic quantum computer," Nature, Nature, vol. 638(8052), pages 912-919, February.
    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. Silva, Gabriel San Martín & Droguett, Enrique López, 2025. "Quantum fault trees and minimal cut sets identification," Reliability Engineering and System Safety, Elsevier, vol. 262(C).
    13. Hannah J. Manetsch & Gyohei Nomura & Elie Bataille & Xudong Lv & Kon H. Leung & Manuel Endres, 2025. "A tweezer array with 6,100 highly coherent atomic qubits," Nature, Nature, vol. 647(8088), pages 60-67, November.
    14. Gabriela Cristescu & Vlad-Florin Drăgoi & Sorin Horaţiu Hoară, 2021. "Generalized Convexity Properties and Shape-Based Approximation in Networks Reliability," Mathematics, MDPI, vol. 9(24), pages 1-21, December.
    15. Lu, Zhao-Hui & Wang, Xiao-Wen & Liu, Liang & Zhang, Xuan-Yi & Li, Chun-Qing, 2025. "An efficient method for network connectivity reliability computation considering correlation of components," Reliability Engineering and System Safety, Elsevier, vol. 257(PA).
    16. 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).
    17. Hao, Zhifeng & Yeh, Wei-Chang, 2025. "GE-MBAT: An efficient algorithm for reliability assessment in multi-state flow networks," Reliability Engineering and System Safety, Elsevier, vol. 260(C).
    18. Paredes, R. & Dueñas-Osorio, L. & Meel, K.S. & Vardi, M.Y., 2019. "Principled network reliability approximation: A counting-based approach," Reliability Engineering and System Safety, Elsevier, vol. 191(C).
    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, 2024. "A novel scanline algorithm for generating ordered variables," Reliability Engineering and System Safety, Elsevier, vol. 252(C).
    2. 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).
    3. 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).
    4. Chan, Jianpeng & Papaioannou, Iason & Straub, Daniel, 2024. "Bayesian improved cross entropy method with categorical mixture models for network reliability assessment," Reliability Engineering and System Safety, Elsevier, vol. 252(C).
    5. Xiao Li & Jia-Yi Hou & Jia-Chao Wang & Guang-Wei Wang & Xiao-Dong He & Feng Zhou & Yi-Bo Wang & Min Liu & Jin Wang & Peng Xu & Ming-Sheng Zhan, 2025. "A fiber array architecture for atom quantum computing," Nature Communications, Nature, vol. 16(1), pages 1-8, December.
    6. Hao, Zhifeng & Yeh, Wei-Chang, 2025. "Applying incremental learning in binary-addition-tree algorithm in reliability analysis of dynamic binary-state networks," Reliability Engineering and System Safety, Elsevier, vol. 261(C).
    7. 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).
    8. Yeh, Wei-Chang, 2024. "Time-reliability optimization for the stochastic traveling salesman problem," Reliability Engineering and System Safety, Elsevier, vol. 248(C).
    9. Hao, Zhifeng & Yeh, Wei-Chang, 2025. "GE-MBAT: An efficient algorithm for reliability assessment in multi-state flow networks," Reliability Engineering and System Safety, Elsevier, vol. 260(C).
    10. Chang, Ping-Chen, 2026. "A cost-reliability trade-off analysis for maintainable multistate flow networks with preventive and corrective maintenance," Reliability Engineering and System Safety, Elsevier, vol. 269(C).
    11. Yeh, Wei-Chang, 2025. "Enhancing reliability calculation for one-output k-out-of-n binary-state networks using a new BAT," Reliability Engineering and System Safety, Elsevier, vol. 257(PA).
    12. 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).
    13. 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.
    14. Wu, Baichao, 2025. "A novel d-flow network decomposition algorithm for fast search and efficient storage of all d-MPs," Reliability Engineering and System Safety, Elsevier, vol. 262(C).
    15. Sultan H Almotiri, 2024. "Quantum-resilient software security: A fuzzy AHP-based assessment framework in the era of quantum computing," PLOS ONE, Public Library of Science, vol. 19(12), pages 1-25, December.
    16. Vivek Katial & Kate Smith-Miles & Charles Hill & Lloyd Hollenberg, 2025. "On the Instance Dependence of Parameter Initialization for the Quantum Approximate Optimization Algorithm: Insights via Instance Space Analysis," INFORMS Journal on Computing, INFORMS, vol. 37(1), pages 146-171, January.
    17. Tong Liu & Shang Liu & Hekang Li & Hao Li & Kaixuan Huang & Zhongcheng Xiang & Xiaohui Song & Kai Xu & Dongning Zheng & Heng Fan, 2023. "Observation of entanglement transition of pseudo-random mixed states," Nature Communications, Nature, vol. 14(1), pages 1-7, December.
    18. Chang, Ping-Chen & Yeh, Cheng-Ta & Cheng, Tzu-Yun & Yu, Vincent F., 2026. "Reliability assessment for multistate semiconductor global logistics networks with freight charges and carbon taxes considerations," Reliability Engineering and System Safety, Elsevier, vol. 269(C).
    19. Sofia Priazhkina & Samuel Palmer & Pablo Martín-Ramiro & Román Orús & Samuel Mugel & Vladimir Skavysh, 2024. "Digital Payments in Firm Networks: Theory of Adoption and Quantum Algorithm," Staff Working Papers 24-17, Bank of Canada.
    20. X. L. He & Yong Lu & D. Q. Bao & Hang Xue & W. B. Jiang & Z. Wang & A. F. Roudsari & Per Delsing & J. S. Tsai & Z. R. Lin, 2023. "Fast generation of Schrödinger cat states using a Kerr-tunable superconducting resonator," Nature Communications, Nature, vol. 14(1), pages 1-10, December.

    More about this item

    Keywords

    ;
    ;
    ;
    ;

    Statistics

    Access and download statistics

    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:270:y:2026:i:c:s0951832025013201. 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.