Bibliographic Details
| Title: |
COUNTING PROBLEMS ASSOCIATED WITH STEINER TREES IN GRAPHS. |
| Authors: |
Provan, J. Scott1 scott_provan@unc.edu, Chari, Manoj K.2 chari@marais.math.lsu.edu |
| Source: |
SIAM Journal on Discrete Mathematics. 1997, Vol. 10 Issue 3, p436-446. 11p. |
| Subjects: |
Graph theory, Tree graphs, Computational mathematics, Combinatorics |
| Abstract: |
This paper considers counting problems associated with K-spanning and K-disconnecting sets for a specified terminal set K in an undirected graph G. In particular, we consider the problems of computing the number of Steiner trees and min K-cuts for G, as well as K-spanning and K-disconnecting sets of cardinality close to the minimum values. Among other things, these numbers are critical to the efficient approximation of K-connected reliability measures in stochastic networks. Although the counting problems considered in this paper are NP-hard in general, a large number of methods for finding shortest paths, min cuts, and Steiner trees in graphs can be extended to efficiently count K-spanning and K-disconnecting sets in important special cases. [ABSTRACT FROM AUTHOR] |
|
Copyright of SIAM Journal on Discrete Mathematics is the property of Society for Industrial & Applied Mathematics and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) |
| Database: |
Engineering Source |
