Adding Learning Capabilities to the LEX Algorithm for Computing Minimal Transversals

Authors

  • Ingrid Guevara Escuela Politécnica Nacional
  • Salvador Godoy-Calderón Instituto Politécnico Nacional
  • Eduardo Alba-Cabrera Universidad San Francisco de Quito

DOI:

https://doi.org/10.13053/cys-27-2-4243

Keywords:

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

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 testor algorithms 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.

Author Biographies

Ingrid Guevara, Escuela Politécnica Nacional

Graduate student

Salvador Godoy-Calderón, Instituto Politécnico Nacional

Centro de Investigación en ComputaciónJefe del Laboratorio de Inteligencia Artificial 

Eduardo Alba-Cabrera, Universidad San Francisco de Quito

Colegio de Ciencias e Ingenierías,Decano del Colegio de Ciencias e Ingenierías

Downloads

Published

2023-06-15

Issue

Vol. 27 No. 2 (2023): 27(2) 2023

Section

Articles

License 

Hereby I transfer exclusively to the Journal "Computación y 
Sistemas", published by the Computing Research Center (CIC-IPN),
the Copyright of the aforementioned paper. I also accept that these 
rights will not be transferred to any other publication, in any other 
format, language or other existing means of developing.
I certify that the paper has not been previously disclosed or simultaneo
usly submitted to any other publication, and that it does not contain 
material whose publication would violate the Copyright or other 
proprietary rights of any person, company or institution. I certify that 
I have the permission from the institution or company where I work or 
study to publish this work.
The representative author accepts the responsibility for the publication
of this paper on behalf of each and every one of the authors. 
This transfer is subject to the following conditions:
  • The authors retain all ownership rights (such as patent rights) of this work, except for the publishing rights transferred to the CIC, through this document.
  • Authors retain the right to publish the work in whole or in part in any book they are the authors or publishers. They can also make use of this work in conferences, courses, personal web pages, and so on.
  • Authors may include working as part of his thesis, for non-profit distribution only.