The complexity of counting cuts and of computing the probability that a graph is connected. (English) Zbl 0524.68041
MSC:
68R10 | Graph theory (including graph drawing) in computer science |
68Q25 | Analysis of algorithms and problem complexity |
05C40 | Connectivity |