Steiner Tree Approximations in Graphs and Hypergraphs

The construction of partial minimum spanning trees being NP-hard, several heuristic algorithms have already been formulated. Many of these heuristics (such as Kruskal’s) use shortest paths to connect the components of the tree. In this work, we present an approximate construction algorithm for the minimum Steiner tree (the optimal tree for diffusion multicast). This construction is based on graph-related structures more advantageous than shortest paths. The algorithm uses connections like simple Steiner trees if necessary. These simple trees can be represented by hyperedges. A hyper metric closure can also be used.