Adding Learning Capabilities to the LEX Algorithm for Computing Minimal Transversals

Ingrid Guevara, Salvador Godoy-Calderon, Eduardo Alba

Research output: Contribution to journalArticlepeer-review

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.

Original languageEnglish
Pages (from-to)357-370
Number of pages14
JournalComputacion y Sistemas
Volume27
Issue number2
DOIs
StatePublished - 26 Jun 2023

Keywords

  • LEX algorithm
  • hypergraph
  • irreducible testor
  • learning strategy
  • minimal transversals

Fingerprint

Dive into the research topics of 'Adding Learning Capabilities to the LEX Algorithm for Computing Minimal Transversals'. Together they form a unique fingerprint.

Cite this