Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

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) 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
and
organization
publishing date
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
2025-11-26 14:53:46
@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}},
}