×
Provan, J. Scott; Ball, Michael O.

The complexity of counting cuts and of computing the probability that a graph is connected. (English) Zbl 0524.68041

SIAM J. Comput. 12, 777-788 (1983).
Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page
scan of Zbl 0524.68041

Cited in 2 Reviews
Cited in 189 Documents

MSC:

68R10 Graph theory (including graph drawing) in computer science
68Q25 Analysis of algorithms and problem complexity
05C40 Connectivity

Keywords:

sharp-P completeness; directed network cuts; vertex covers; bipartite graph; antichains; partial order; network reliability
Cite Review PDF
Full Text: DOI