@article{Molnár2026, 
author = {Miklós Molnár},
title = {Hypergraphs for Covering Trees and Approximating Steiner Trees},
year = {2026},
journal = {Computers, Materials & Continua},
volume = {88},
number = {1},
keywords = {Graphs, spanning problems, hypergraphs, steiner problem, metric closure, approximation},
url = {https://www.sciopen.com/article/10.32604/cmc.2026.077825},
doi = {10.32604/cmc.2026.077825},
abstract = {This article presents a particular tree covering technique. To cover a set of nodes belonging to an unknown tree, a set of connected small Steiner trees is proposed. These Steiner trees can be represented as hyperedges, and a chain or tree of hyperedges provides the cover. The model allows the calculation of approximate (partial) spanning trees in graphs. The idea of covering a set of nodes by hyperedges can be used directly in Steiner heuristics. The NP-hard Steiner problem in graphs is one of the most studied graph-related problems. Several heuristics are known to give approximated solutions. The classical approximations of the Steiner problem apply shortest paths. We present a generalized metric closure that can be constructed from hyperedges of limited size, and new approximations based on the generalized metric closure are proposed. A connected hyperedge set (without loops) approximates a Steiner tree. The paper also presents a performance analysis of the proposed heuristics. The variation in hyperedge size is analyzed. An interesting result is that using larger hyperedges significantly improves the algorithm’s efficiency.}
}