全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...

The Exponential Time Complexity of Computing the Probability That a Graph is Connected

DOI: 10.1007/978-3-642-17493-3_19

Full-Text   Cite this paper   Add to My Lib

Abstract:

We show that for every probability p with 0 < p < 1, computation of all-terminal graph reliability with edge failure probability p requires time exponential in Omega(m/ log^2 m) for simple graphs of m edges under the Exponential Time Hypothesis.

Full-Text

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133