The exponential time complexity of computing the probability that a graph is connected
(2010) 5th International Symposium on Parameterized and Exact Computation (IPEC 2010) 6198. p.192-203- 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.
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/1664211
- author
- Husfeldt, Thore LU and Taslaman, Nina
- organization
- publishing date
- 2010
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- host publication
- Lecture Notes in Computer Science
- volume
- 6198
- pages
- 11 pages
- publisher
- Springer
- conference name
- 5th International Symposium on Parameterized and Exact Computation (IPEC 2010)
- conference location
- Chennai, India
- conference dates
- 2010-12-13 - 2010-12-15
- external identifiers
-
- scopus:78650903868
- project
- Exact algorithms
- language
- English
- LU publication?
- yes
- id
- e483aed8-f5dd-439b-8b13-9a61537e5e0a (old id 1664211)
- date added to LUP
- 2016-04-04 10:34:23
- date last changed
- 2022-01-29 20:31:33
@inproceedings{e483aed8-f5dd-439b-8b13-9a61537e5e0a, 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 = {{Husfeldt, Thore and Taslaman, Nina}}, booktitle = {{Lecture Notes in Computer Science}}, language = {{eng}}, pages = {{192--203}}, publisher = {{Springer}}, title = {{The exponential time complexity of computing the probability that a graph is connected}}, volume = {{6198}}, year = {{2010}}, }