---
_id: '6918'
abstract:
- lang: eng
  text: "We consider the classic problem of Network Reliability. A network is given
    together with a source vertex, one or more target vertices, and probabilities
    assigned to each of the edges. Each edge of the network is operable with its associated
    probability and the problem is to determine the probability of having at least
    one source-to-target path that is entirely composed of operable edges. This problem
    is known to be NP-hard.\r\n\r\nWe provide a novel scalable algorithm to solve
    the Network Reliability problem when the treewidth of the underlying network is
    small. We also show our algorithm’s applicability for real-world transit networks
    that have small treewidth, including the metro networks of major cities, such
    as London and Tokyo. Our algorithm leverages tree decompositions to shrink the
    original graph into much smaller graphs, for which reliability can be efficiently
    and exactly computed using a brute force method. To the best of our knowledge,
    this is the first exact algorithm for Network Reliability that can scale to handle
    real-world instances of the problem."
acknowledgement: We are grateful to the anonymous reviewers for their comments, which
  significantly improved the present work. The research was partially supported by
  the EPSRC Early Career Fellowship EP/R023379/1, grant no. SC7-1718-01 of the London
  Mathematical Society, an IBM PhD Fellowship, and a DOC Fellowship of the Austrian
  Academy of Sciences (ÖAW).
article_number: '106665'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Amir Kafshdar
  full_name: Goharshady, Amir Kafshdar
  id: 391365CE-F248-11E8-B48F-1D18A9856A87
  last_name: Goharshady
  orcid: 0000-0003-1702-6584
- first_name: Fatemeh
  full_name: Mohammadi, Fatemeh
  last_name: Mohammadi
citation:
  ama: Goharshady AK, Mohammadi F. An efficient algorithm for computing network reliability
    in small treewidth. <i>Reliability Engineering and System Safety</i>. 2020;193.
    doi:<a href="https://doi.org/10.1016/j.ress.2019.106665">10.1016/j.ress.2019.106665</a>
  apa: Goharshady, A. K., &#38; Mohammadi, F. (2020). An efficient algorithm for computing
    network reliability in small treewidth. <i>Reliability Engineering and System
    Safety</i>. Elsevier. <a href="https://doi.org/10.1016/j.ress.2019.106665">https://doi.org/10.1016/j.ress.2019.106665</a>
  chicago: Goharshady, Amir Kafshdar, and Fatemeh Mohammadi. “An Efficient Algorithm
    for Computing Network Reliability in Small Treewidth.” <i>Reliability Engineering
    and System Safety</i>. Elsevier, 2020. <a href="https://doi.org/10.1016/j.ress.2019.106665">https://doi.org/10.1016/j.ress.2019.106665</a>.
  ieee: A. K. Goharshady and F. Mohammadi, “An efficient algorithm for computing network
    reliability in small treewidth,” <i>Reliability Engineering and System Safety</i>,
    vol. 193. Elsevier, 2020.
  ista: Goharshady AK, Mohammadi F. 2020. An efficient algorithm for computing network
    reliability in small treewidth. Reliability Engineering and System Safety. 193,
    106665.
  mla: Goharshady, Amir Kafshdar, and Fatemeh Mohammadi. “An Efficient Algorithm for
    Computing Network Reliability in Small Treewidth.” <i>Reliability Engineering
    and System Safety</i>, vol. 193, 106665, Elsevier, 2020, doi:<a href="https://doi.org/10.1016/j.ress.2019.106665">10.1016/j.ress.2019.106665</a>.
  short: A.K. Goharshady, F. Mohammadi, Reliability Engineering and System Safety
    193 (2020).
date_created: 2019-09-29T22:00:44Z
date_published: 2020-01-01T00:00:00Z
date_updated: 2024-03-25T23:30:18Z
day: '01'
department:
- _id: KrCh
doi: 10.1016/j.ress.2019.106665
external_id:
  arxiv:
  - '1712.09692'
  isi:
  - '000501641400050'
intvolume: '       193'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1712.09692
month: '01'
oa: 1
oa_version: Preprint
project:
- _id: 266EEEC0-B435-11E9-9278-68D0E5697425
  name: Quantitative Game-theoretic Analysis of Blockchain Applications and Smart
    Contracts
publication: Reliability Engineering and System Safety
publication_identifier:
  issn:
  - '09518320'
publication_status: published
publisher: Elsevier
quality_controlled: '1'
related_material:
  record:
  - id: '8934'
    relation: dissertation_contains
    status: public
scopus_import: '1'
status: public
title: An efficient algorithm for computing network reliability in small treewidth
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 193
year: '2020'
...