TY  - EJOU
AU  - Molnár, Miklós 

TI  - Hypergraphs for Covering Trees and Approximating Steiner Trees
T2  - Computers, Materials \& Continua

PY  - 2026
VL  - 88
IS  - 1
SN  - 1546-2226

AB  - 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.
KW  - Graphs; spanning problems; hypergraphs; steiner problem; metric closure; approximation

DO  - 10.32604/cmc.2026.077825