Szathmáry, László (2023) An incremental algorithm for computing the transversal hypergraph. Annales Mathematicae et Informaticae, 58.. pp. 147-159. ISSN 17876117
|
Text
AMI_58_from147to159.pdf - Published Version Download (821kB) | Preview |
Official URL: http://doi.org/10.33039/ami.2023.08.007
Abstract
In this paper we present an incremental algorithm for computing the transversal hypergraph. Our algorithm is an optimized version of Berge’s algorithm for solving the transversal hypergraph problem. The original algorithm of Berge is the simplest and most direct scheme for generating all minimal transversals of a hypergraph. Here we present an optimized version of Berge’s algorithm that we call BergeOpt. We show that BergeOpt can significantly reduce the number of expensive inclusion tests.
| Item Type: | Article |
|---|---|
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika > QA76 Computer software / programozás |
| Depositing User: | Tibor Gál |
| Date Deposited: | 13 Nov 2023 12:56 |
| Last Modified: | 13 Nov 2023 12:56 |
| URI: | http://real.mtak.hu/id/eprint/179784 |
Actions (login required)
 |
Edit Item |
