Open Access

ARTICLE

Hypergraphs for Covering Trees and Approximating Steiner Trees

Miklós Molnár^*

LIRMM, University of Montpellier, CNRS, Montpellier, France

* Corresponding Author: Miklós Molnár. Email:

Computers, Materials & Continua 2026, 88(1), 94 https://doi.org/10.32604/cmc.2026.077825

Received 17 December 2025; Accepted 17 April 2026; Issue published 08 May 2026

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.

---

Keywords

---