File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.4230/LIPIcs.ICALP.2024.62
- Scopus: eid_2-s2.0-85198349708
- Find via
Supplementary
-
Citations:
- Scopus: 0
- Appears in Collections:
Conference Paper: An FPRAS for Two Terminal Reliability in Directed Acyclic Graphs
Title | An FPRAS for Two Terminal Reliability in Directed Acyclic Graphs |
---|---|
Authors | |
Keywords | Approximate counting Network reliability Sampling algorithm |
Issue Date | 2024 |
Citation | Leibniz International Proceedings in Informatics, LIPIcs, 2024, v. 297, article no. 62 How to Cite? |
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. |
Persistent Identifier | http://hdl.handle.net/10722/355031 |
ISSN | 2023 SCImago Journal Rankings: 0.796 |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Feng, Weiming | - |
dc.contributor.author | Guo, Heng | - |
dc.date.accessioned | 2025-03-21T09:10:44Z | - |
dc.date.available | 2025-03-21T09:10:44Z | - |
dc.date.issued | 2024 | - |
dc.identifier.citation | Leibniz International Proceedings in Informatics, LIPIcs, 2024, v. 297, article no. 62 | - |
dc.identifier.issn | 1868-8969 | - |
dc.identifier.uri | http://hdl.handle.net/10722/355031 | - |
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. | - |
dc.language | eng | - |
dc.relation.ispartof | Leibniz International Proceedings in Informatics, LIPIcs | - |
dc.subject | Approximate counting | - |
dc.subject | Network reliability | - |
dc.subject | Sampling algorithm | - |
dc.title | An FPRAS for Two Terminal Reliability in Directed Acyclic Graphs | - |
dc.type | Conference_Paper | - |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.doi | 10.4230/LIPIcs.ICALP.2024.62 | - |
dc.identifier.scopus | eid_2-s2.0-85198349708 | - |
dc.identifier.volume | 297 | - |
dc.identifier.spage | article no. 62 | - |
dc.identifier.epage | article no. 62 | - |