COUNTING PROBLEMS ASSOCIATED WITH STEINER TREES IN GRAPHS.
Saved in:
| 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 |
| FullText | Links: – Type: pdflink Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 13219682 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: COUNTING PROBLEMS ASSOCIATED WITH STEINER TREES IN GRAPHS. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Provan%2C+J%2E+Scott%22">Provan, J. Scott</searchLink><relatesTo>1</relatesTo><i> scott_provan@unc.edu</i><br /><searchLink fieldCode="AR" term="%22Chari%2C+Manoj+K%2E%22">Chari, Manoj K.</searchLink><relatesTo>2</relatesTo><i> chari@marais.math.lsu.edu</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22SIAM+Journal+on+Discrete+Mathematics%22">SIAM Journal on Discrete Mathematics</searchLink>. 1997, Vol. 10 Issue 3, p436-446. 11p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Graph+theory%22">Graph theory</searchLink><br /><searchLink fieldCode="DE" term="%22Tree+graphs%22">Tree graphs</searchLink><br /><searchLink fieldCode="DE" term="%22Computational+mathematics%22">Computational mathematics</searchLink><br /><searchLink fieldCode="DE" term="%22Combinatorics%22">Combinatorics</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: 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] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>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.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=13219682 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1137/S0895480194262862 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 11 StartPage: 436 Subjects: – SubjectFull: Graph theory Type: general – SubjectFull: Tree graphs Type: general – SubjectFull: Computational mathematics Type: general – SubjectFull: Combinatorics Type: general Titles: – TitleFull: COUNTING PROBLEMS ASSOCIATED WITH STEINER TREES IN GRAPHS. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Provan, J. Scott – PersonEntity: Name: NameFull: Chari, Manoj K. IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 08 Text: 1997 Type: published Y: 1997 Identifiers: – Type: issn-print Value: 08954801 Numbering: – Type: volume Value: 10 – Type: issue Value: 3 Titles: – TitleFull: SIAM Journal on Discrete Mathematics Type: main |
| ResultId | 1 |
