{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T14:40:34Z","timestamp":1773931234303,"version":"3.50.1"},"reference-count":25,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T00:00:00Z","timestamp":1773878400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>The construction of partial minimum spanning trees is an NP-hard problem, leading to the development of various heuristic algorithms. Existing heuristics, including Kruskal\u2019s algorithm, frequently employ shortest paths to connect tree components. This study introduces an approximate algorithm for constructing the minimum Steiner tree, which serves as the optimal structure for diffusion multicast. The proposed approach utilizes graph-based structures that provide advantages over conventional shortest-path methods. The algorithm incorporates connections analogous to those in simple Steiner trees when required. These simple trees are represented by hyperedges, and a Hyper Metric Closure can also be applied. Experimental results indicate that this hypergraph-based method enables constructions that more closely approximate the optimal Steiner tree cost compared to traditional pairwise techniques, offering a scalable balance between computational complexity and routing efficiency.<\/jats:p>","DOI":"10.3390\/a19030232","type":"journal-article","created":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T11:50:36Z","timestamp":1773921036000},"page":"232","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Steiner Tree Approximations in Graphs and Hypergraphs"],"prefix":"10.3390","volume":"19","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1345-4792","authenticated-orcid":false,"given":"Mikl\u00f3s","family":"Moln\u00e1r","sequence":"first","affiliation":[{"name":"Laboratoire d\u2019Informatique, de Robotique et de Micro\u00e9lectronique de Montpellier (LIRMM), University of Montpellier, Centre National de la Recherche Scientifique (CNRS), 161 Rue Ada, 34095 Montpellier Cedex 5, France"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7802-3681","authenticated-orcid":false,"given":"Basma Mostafa","family":"Hassan","sequence":"additional","affiliation":[{"name":"Operations Research Department, Faculty of Computers & Artificial Intelligence, Cairo University, Giza 12613, Egypt"},{"name":"Faculty of Artificial Intelligence & Informatics, Horus University, New Damietta 34518, Egypt"}]}],"member":"1968","published-online":{"date-parts":[[2026,3,19]]},"reference":[{"key":"ref_1","unstructured":"Hwang, F., Richards, D., and Winter, P. (1992). The Steiner Tree Problem, North Holland. Annals of discrete mathematics."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1090\/S0002-9939-1956-0078686-7","article-title":"On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem","volume":"7","author":"Kruskal","year":"1956","journal-title":"Proc. Am. Math. Soc."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"1389","DOI":"10.1002\/j.1538-7305.1957.tb01515.x","article-title":"Shortest connection networks and some generalizations","volume":"36","author":"Prim","year":"1957","journal-title":"Bell Syst. Tech. J."},{"key":"ref_4","first-page":"573","article-title":"An approximate solution for the Steiner problem in graphs","volume":"24","author":"Takahashi","year":"1981","journal-title":"Math. Jpn."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1007\/BF00288961","article-title":"A fast algorithm for Steiner trees","volume":"15","author":"Kou","year":"1981","journal-title":"Acta Inform."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1016\/S0167-5060(08)70655-1","article-title":"An 11\/6-Approximation Algorithm for the Steiner Problem on Graphs","volume":"Volume 51","author":"Fiedler","year":"1992","journal-title":"Fourth Czechoslovakian Symposium on Combinatorics, Graphs and Complexity"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Du, D.Z., Zhang, Y., and Feng, Q. (1991). On better heuristic for Euclidean Steiner minimum trees. Proceedings of the 1991 32nd Annual Symposium of Foundations of Computer Science, IEEE.","DOI":"10.1109\/SFCS.1991.185402"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1007\/BF01581080","article-title":"On better heuristics for Steiner minimum trees","volume":"57","author":"Du","year":"1992","journal-title":"Math. Program."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Byrka, J., Grandoni, F., Rothvo\u00df, T., and Sanit\u00e0, L. (2010). An improved LP-based approximation for Steiner tree. Proceedings of the Forty-Second ACM Symposium on Theory of Computing, STOC \u201910, Association for Computing Machinery.","DOI":"10.1145\/1806689.1806769"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Legrand, P., Liefooghe, A., Lepagnot, J., Monmarch\u00e9, N., Idoumghar, L., Pallez, D., Siarry, P., and Lutton, E. (2026). Comparing Quantum Annealer and Metaheuristic Methods to Solve the Steiner Tree Problem. Proceedings of the Artificial Evolution, Springer.","DOI":"10.1007\/978-3-032-07998-5"},{"key":"ref_11","unstructured":"Zhang, J., and Ajwani, D. (2022). Learning to Prune Instances of Steiner Tree Problem in Graphs. Proceedings of the 2022 International Network Optimization Conference, OpenProceedings.org."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Ria\u00f1o-Enciso, L.M., Cort\u00e9s-Caicedo, B., Montoya, O.D., Grisales-Nore\u00f1a, L.F., and Hern\u00e1ndez, J.C. (2025). Sustainable Metaheuristic-Based Planning of Rural Medium- Voltage Grids: A Comparative Study of Spanning and Steiner Tree Topologies for Cost-Efficient Electrification. Sustainability, 17.","DOI":"10.3390\/su17188145"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"e70040","DOI":"10.1002\/cpe.70040","article-title":"Dynamic Algorithms for Approximate Steiner Trees","volume":"37","author":"Raikwar","year":"2025","journal-title":"Concurr. Comput. Pract. Exp."},{"key":"ref_14","unstructured":"University of Bonn (2026, March 11). Steiner Tree Compendium. Available online: https:\/\/theory.cs.uni-bonn.de\/info5\/steinerkompendium\/."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1002\/net.22005","article-title":"Solving Steiner trees: Recent advances, challenges, and perspectives","volume":"77","year":"2021","journal-title":"Networks"},{"key":"ref_16","first-page":"357","article-title":"A new exact algorithm for rectilinear Steiner trees","volume":"Volume 40","author":"Warme","year":"1998","journal-title":"Proceedings of the 1997 Network Design: Connectivity and Facilities Location, DIMACS Series in Discrete Mathematics and Theoretical Computer Science"},{"key":"ref_17","unstructured":"Warme, D.M. (1998). Spanning Trees in Hypergraphs with Applications to Steiner Trees. [Ph.D. Thesis, University of Virginia]."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1006\/jagm.2000.1086","article-title":"A New Approximation Algorithm for the Steiner Tree Problem with Performance Ratio 5\/3","volume":"36","author":"Steger","year":"2000","journal-title":"J. Algorithms"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Tollis, I.G., and Patrignani, M. (2009). Subdivision Drawings of Hypergraphs. Graph Drawing, Springer.","DOI":"10.1007\/978-3-642-00219-9"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Brazil, M., and Zachariasen, M. (2015). Steiner Trees in Graphs and Hypergraphs. Optimal Interconnection Trees in the Plane: Theory, Algorithms and Applications, Springer International Publishing.","DOI":"10.1007\/978-3-319-13915-9"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/S0167-6377(02)00185-2","article-title":"On Steiner trees and minimum spanning trees in hypergraphs","volume":"31","author":"Polzin","year":"2003","journal-title":"Oper. Res. Lett."},{"key":"ref_22","unstructured":"Molnar, M. (1998). Construction D\u2019arbres de Diffusion Multicast Bas\u00e9e sur une Modification de L\u2019heuristique de Kruskal, INRIA. Technical Report 3587."},{"key":"ref_23","unstructured":"Marie, R., and Molnar, M. (1999). Arbre Couvrant Partiel Pseudo-Optimal Pour Diffusion Multipoint, INRIA. Technical Report 3636."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"41","DOI":"10.15837\/ijccc.2006.1.2271","article-title":"An Exact Algorithm for Steiner Tree Problem on Graphs","volume":"1","author":"Stanojevic","year":"2006","journal-title":"Int. J. Comput. Commun. Control"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"122","DOI":"10.1137\/S0895480101393155","article-title":"Tighter Bounds for Graph Steiner Tree Approximation","volume":"19","author":"Robins","year":"2005","journal-title":"SIAM J. Discrete Math."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/19\/3\/232\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T11:56:26Z","timestamp":1773921386000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/19\/3\/232"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,3,19]]},"references-count":25,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2026,3]]}},"alternative-id":["a19030232"],"URL":"https:\/\/doi.org\/10.3390\/a19030232","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,3,19]]}}}