An FPRAS for Two Terminal Reliability in Directed Acyclic Graphs
dc.contributor.author
Feng, Weiming
dc.contributor.author
Guo, Heng
dc.contributor.editor
Bringmann, Karl
dc.contributor.editor
Grohe, Martin
dc.contributor.editor
Puppis, Gabriele
dc.contributor.editor
Svensson, Ola
dc.date.accessioned
2024-07-23T14:32:29Z
dc.date.available
2024-07-19T06:10:30Z
dc.date.available
2024-07-23T14:32:29Z
dc.date.issued
2024-07
dc.identifier.isbn
978-3-95977-322-5
en_US
dc.identifier.issn
1868-8969
dc.identifier.other
10.4230/LIPIcs.ICALP.2024.62
en_US
dc.identifier.uri
http://hdl.handle.net/20.500.11850/683864
dc.identifier.doi
10.3929/ethz-b-000683864
dc.description.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.
en_US
dc.format
application/pdf
en_US
dc.language.iso
en
en_US
dc.publisher
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
en_US
dc.rights.uri
http://creativecommons.org/licenses/by/4.0/
dc.subject
Approximate counting
en_US
dc.subject
Network reliability
en_US
dc.subject
Sampling algorithm
en_US
dc.title
An FPRAS for Two Terminal Reliability in Directed Acyclic Graphs
en_US
dc.type
Conference Paper
dc.rights.license
Creative Commons Attribution 4.0 International
dc.date.published
2024-07-02
ethz.book.title
51st International Colloquium on Automata, Languages, and Programming
en_US
ethz.journal.title
Leibniz International Proceedings in Informatics (LIPIcs)
ethz.journal.volume
297
en_US
ethz.journal.abbreviated
Leibniz Int. Proc. Inform.
ethz.pages.start
62:1
en_US
ethz.pages.end
62:19
en_US
ethz.version.deposit
publishedVersion
en_US
ethz.event
51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
en_US
ethz.event.location
Tallinn, Estonia
en_US
ethz.event.date
July 8-12, 2024
en_US
ethz.identifier.scopus
ethz.identifier.arxiv
2310.00938
ethz.publication.place
Saarbrücken
en_US
ethz.publication.status
published
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00003 - Schulleitung und Dienste::00022 - Bereich VP Forschung / Domain VP Research::02889 - ETH Institut für Theoretische Studien / ETH Institute for Theoretical Studies
ethz.date.deposited
2024-07-19T06:10:33Z
ethz.source
SCOPUS
ethz.eth
yes
en_US
ethz.availability
Open access
en_US
ethz.rosetta.installDate
2024-07-23T14:32:31Z
ethz.rosetta.lastUpdated
2024-07-23T14:32:31Z
ethz.rosetta.exportRequired
true
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=An%20FPRAS%20for%20Two%20Terminal%20Reliability%20in%20Directed%20Acyclic%20Graphs&rft.jtitle=Leibniz%20International%20Proceedings%20in%20Informatics%20(LIPIcs)&rft.date=2024-07&rft.volume=297&rft.spage=62:1&rft.epage=62:19&rft.issn=1868-8969&rft.au=Feng,%20Weiming&Guo,%20Heng&rft.isbn=978-3-95977-322-5&rft.genre=proceeding&rft_id=info:doi/10.4230/LIPIcs.ICALP.2024.62&rft.btitle=51st%20International%20Colloquium%20on%20Automata,%20Languages,%20and%20Programming
Files in this item
Publication type
-
Conference Paper [35865]