An FPRAS for Two Terminal Reliability in Directed Acyclic Graphs
Open access
Date
2024-07Type
- Conference Paper
ETH Bibliography
yes
Altmetrics
Abstract
We give a fully polynomial-time randomized approximation scheme (FPRAS) for two terminal reliability in directed acyclic graphs (DAGs). In contrast, we also show the complementing problem of approximating two terminal unreliability in DAGs is #BIS-hard.
Permanent link
https://doi.org/10.3929/ethz-b-000683864Publication status
publishedEditor
Book title
51st International Colloquium on Automata, Languages, and ProgrammingJournal / series
Leibniz International Proceedings in Informatics (LIPIcs)Volume
Pages / Article No.
Publisher
Schloss Dagstuhl - Leibniz-Zentrum für InformatikEvent
Subject
Approximate counting; Network reliability; Sampling algorithmOrganisational unit
02889 - ETH Institut für Theoretische Studien / ETH Institute for Theoretical Studies
More
Show all metadata
ETH Bibliography
yes
Altmetrics