The Exponential Time Complexity of Computing the Probability That a Graph is Connected
classification
💻 cs.CC
keywords
exponentialprobabilitytimegraphall-terminalcomplexitycomputationcomputing
read the original 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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.