scientific article; zbMATH DE number 3985248

From MaRDI portal
Publication:3749073





[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.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3749073)