Advanced

The exponential time complexity of computing the probability that a graph is connected

Husfeldt, Thore LU and Taslaman, Nina (2010) 5th International Symposium on Parameterized and Exact Computation (IPEC 2010) In Lecture Notes in Computer Science 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:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
in
Lecture Notes in Computer Science
volume
6198
pages
11 pages
publisher
Springer
conference name
5th International Symposium on Parameterized and Exact Computation (IPEC 2010)
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
2010-08-31 09:22:42
date last changed
2017-03-26 04:33:34
@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},
}