File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: An FPRAS for Two Terminal Reliability in Directed Acyclic Graphs

TitleAn FPRAS for Two Terminal Reliability in Directed Acyclic Graphs
Authors
Feng, WeimingGuo, Heng
KeywordsApproximate counting
Network reliability
Sampling algorithm
Issue Date2024
Citation
Leibniz International Proceedings in Informatics, LIPIcs, 2024, v. 297, article no. 62 How to Cite?
DOI: http://dx.doi.org/10.4230/LIPIcs.ICALP.2024.62
AbstractWe 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 Identifierhttp://hdl.handle.net/10722/355031
ISSN
1868-8969
2023 SCImago Journal Rankings: 0.796

 

DC FieldValueLanguage
dc.contributor.authorFeng, Weiming-
dc.contributor.authorGuo, Heng-
dc.date.accessioned2025-03-21T09:10:44Z-
dc.date.available2025-03-21T09:10:44Z-
dc.date.issued2024-
dc.identifier.citationLeibniz International Proceedings in Informatics, LIPIcs, 2024, v. 297, article no. 62-
dc.identifier.issn1868-8969-
dc.identifier.urihttp://hdl.handle.net/10722/355031-
dc.description.abstractWe 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.languageeng-
dc.relation.ispartofLeibniz International Proceedings in Informatics, LIPIcs-
dc.subjectApproximate counting-
dc.subjectNetwork reliability-
dc.subjectSampling algorithm-
dc.titleAn FPRAS for Two Terminal Reliability in Directed Acyclic Graphs-
dc.typeConference_Paper-
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.4230/LIPIcs.ICALP.2024.62-
dc.identifier.scopuseid_2-s2.0-85198349708-
dc.identifier.volume297-
dc.identifier.spagearticle no. 62-
dc.identifier.epagearticle no. 62-

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats