COUNTING PROBLEMS ASSOCIATED WITH STEINER TREES IN GRAPHS

This paper considers counting problems associated with K-spanning and K-disconnecting sets for a specified terminal set K in an undirected g raph G. In particular, we consider the problems of computing the numbe r of Steiner trees and min K-cuts for G, as well as K-spanning and K-d isconnecting sets of cardinality close to the minimum values. Among ot her things, these numbers are critical to the efficient approximation of K-connected reliability measures in stochastic networks. Although t he counting problems considered in this paper are NP-hard in general, a large number of methods for finding shortest paths, min cuts, and St einer trees in graphs can be extended to efficiently count K-spanning and K-disconnecting sets in important special cases.