scientific article; zbMATH DE number 3985248
[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.
- Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation
- Steiner's problem in graphs: Heuristic methods
- The competitiveness of randomized algorithms for on-line Steiner tree and on-line spanning tree problems
- Analysis of Steiner subtrees of random trees for traceroute algorithms
- Near optimal bounds for Steiner trees in the hypercube
- Shortest‐path metric approximation for random subgraphs
- A sharp threshold for minimum bounded-depth and bounded-diameter spanning trees and Steiner trees in random networks
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)