| Journal: | Computación y sistemas |
| Database: | |
| System number: | 000560798 |
| ISSN: | 1405-5546 |
| Authors: | Guevara, Ingrid1 Godoy Calderon, Salvador2 Alba, Eduardo3 |
| Institutions: | 1Escuela Politécnica Nacional, Quito, Quito. Ecuador 2Instituto Politécnico Nacional, Centro de Investigación en Computación, Mexico City. México 3Universidad San Francisco de Quito, Colegio de Ciencias e Ingenierías, Quito. Ecuador |
| Year: | 2023 |
| Season: | Abr-Jun |
| Volumen: | 27 |
| Number: | 2 |
| Pages: | 357-370 |
| Country: | México |
| Language: | Inglés |
| English abstract | Despite being little known and poorly documented, LEX is part of the family of typical testors-finding algorithms that generally has better performance than other much more divulged similar algorithms. The recently published relationship between typical testors and minimal hitting sets, potentially extends the usefulness and applicability of this algorithm to the hypergraphs and data mining fields. Unfortunately, the high time-complexity of both typical testors and minimal hitting sets algorithms still remains a major obstacle. Therefore, alternatives that can help overcome difficult problems are constantly being researched. In this paper we propose the inclusion of a symbolic learning behavior into the implementation of the LEX algorithm. The incorporated symbolic learning is a general strategy for optimizing the search process, and thus improves the efficiency of minimal transversals and typical testors algorithms. In addition, the performance of the resulting algorithm is assessed by using carefully designed benchmark test matrices. |
| Keyword: | LEX algorithm, Learning strategy, Minimal transversals, Hypergraph, Irreducible testor |
| Full text: | Texto completo (Ver HTML) Texto completo (Ver PDF) |
