The Exponential Time Complexity of Computing the Probability That a Graph Is Connected

DOI10.1007/978-3-642-17493-3_19zbMath1253.68176arXiv1009.2363OpenAlexW2210185040MaRDI QIDQ3058703

Nina Taslaman, Thore Husfeldt

Publication date: 7 December 2010

Published in: Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1009.2363

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Connectivity (05C40)

Related Items (2)

Block interpolation: a framework for tight exponential-time counting complexity ⋮ Fine-grained dichotomies for the Tutte plane and Boolean \#CSP

Uses Software

• tutte_bhkk

Cites Work

• Unnamed Item
• Unnamed Item
• Inapproximability of the Tutte polynomial
• Which problems have strongly exponential complexity?
• New upper bound for the \#3-SAT problem
• The Tutte Polynomial Part I: General Theory
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• Exponential Time Complexity of Weighted Counting of Independent Sets
• The Travelling Salesman Problem in Bounded Degree Graphs
• Exponential Time Complexity of the Permanent and the Tutte Polynomial
• The Complexity of Enumeration and Reliability Problems
• A recursive algorithm for finding reliability measures related to the connection of nodes in a graph
• On the computational complexity of the Jones and Tutte polynomials

This page was built for publication: The Exponential Time Complexity of Computing the Probability That a Graph Is Connected