---
res:
bibo_abstract:
- "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.@eng"
bibo_authorlist:
- foaf_Person:
foaf_givenName: Amir Kafshdar
foaf_name: Goharshady, Amir Kafshdar
foaf_surname: Goharshady
foaf_workInfoHomepage: http://www.librecat.org/personId=391365CE-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0003-1702-6584
- foaf_Person:
foaf_givenName: Fatemeh
foaf_name: Mohammadi, Fatemeh
foaf_surname: Mohammadi
bibo_doi: 10.1016/j.ress.2019.106665
bibo_volume: 193
dct_date: 2020^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/09518320
dct_language: eng
dct_publisher: Elsevier@
dct_title: An efficient algorithm for computing network reliability in small treewidth@
...