An FPRAS for Two Terminal Reliability in Directed Acyclic Graphs
OPEN ACCESS
Loading...
Author / Producer
Date
2024-07
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
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
Publication status
published
Book title
51st International Colloquium on Automata, Languages, and Programming
Volume
297
Pages / Article No.
Publisher
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Event
51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Approximate counting; Network reliability; Sampling algorithm
Organisational unit
02889 - ETH Institut für Theoretische Studien / ETH Institute for Theoretical Studies