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

      0 references
      0 references
      0 references
      1986
      0 references
      polynomial algorithms
      0 references
      finding minimum Steiner trees
      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

      Identifiers

      0 references
      0 references
      0 references
      0 references