No label defined (Q3749073)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3985248
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 3985248 |
Statements
1986
0 references
polynomial algorithms
0 references
finding minimum Steiner trees
0 references
0.8214174509048462
0 references
0.8184981346130371
0 references
0.8152322173118591
0 references
[For the entire collection see Zbl 0596.00021.] The paper contains a probabilistic study of two different polynomial algorithms for finding minimum Steiner trees. It means, results are presented which hold almost surely, that is for almost all graphs. The problem is defined as follows: given a graph \(G=(V,E)\) and a subset of its vertices \(Y\subset V\) find the smallest (i.e. with the smallest possible number of vertices) tree of G spanning all the vertices of Y whose leaves are from Y. The main results show that regardless the fact that the problem is NP-complete solutions which are arbitrarily close to the optimal solution can be achieved by polynomial algorithms.
0 references