@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",

}