@inproceedings{e483aed8f5dd439b8b139a61537e5e0a,
title = "The exponential time complexity of computing the probability that a graph is connected",
abstract = "We show that computation of all-terminal graph reliability requires time exponential in Ω(m/ log2 m) for simple graphs of m edges under the Exponential Time Hypothesis.",
author = "Thore Husfeldt and Nina Taslaman",
year = "2010",
language = "English",
volume = "6198",
publisher = "Springer",
pages = "192--203",
booktitle = "Lecture Notes in Computer Science",
address = "Germany",
note = "5th International Symposium on Parameterized and Exact Computation (IPEC 2010) ; Conference date: 13-12-2010 Through 15-12-2010",
}