On the Relation between the Concepts of Irreducible Testor and Minimal Transversal

Eduardo Alba-Cabrera; Salvador Godoy-Calderon; Manuel S. Lazo-Cortes; J. Fco Martinez-Trinidad; Jesus A. Carrasco-Ochoa

doi:10.1109/ACCESS.2019.2922231

On the Relation between the Concepts of Irreducible Testor and Minimal Transversal

Eduardo Alba-Cabrera, Salvador Godoy-Calderon, Manuel S. Lazo-Cortes, J. Fco Martinez-Trinidad, Jesus A. Carrasco-Ochoa

Centro de Investigación en Computación (CIC)

Research output: Contribution to journal › Article › peer-review

8 Scopus citations

Abstract

This paper aims at studying the relationship between two rather relevant theoretic fields such as Graph Theory and Testor Theory, deepening in the unexploited relation between the concepts of Minimal Transversal and Irreducible Testor. First, the classic definitions of each concept are provided, and then the relation between them is shown and formalized. Some of the immediate consequences of this relation, in terms of the duality property of transversals and about the equivalence of the result of two specific algorithms, one from each field, are discussed. Finally, we also discuss several future research directions that arise from the relationship between the concepts of Minimal Transversal And Irreducible Testor, and the way in which those directions can potentially benefit the development of theory and algorithms for solving different practical problems in both areas.

Original language	English
Article number	8735693
Pages (from-to)	82809-82816
Number of pages	8
Journal	IEEE Access
Volume	7
DOIs	https://doi.org/10.1109/ACCESS.2019.2922231
State	Published - 2019

Keywords

Graph theory
Hitting set
Irreducible testor
Minimal transversal
Testor theory

Access to Document

10.1109/ACCESS.2019.2922231

Cite this

@article{f83083e567564ddea000d5d01714a407,

title = "On the Relation between the Concepts of Irreducible Testor and Minimal Transversal",

abstract = "This paper aims at studying the relationship between two rather relevant theoretic fields such as Graph Theory and Testor Theory, deepening in the unexploited relation between the concepts of Minimal Transversal and Irreducible Testor. First, the classic definitions of each concept are provided, and then the relation between them is shown and formalized. Some of the immediate consequences of this relation, in terms of the duality property of transversals and about the equivalence of the result of two specific algorithms, one from each field, are discussed. Finally, we also discuss several future research directions that arise from the relationship between the concepts of Minimal Transversal And Irreducible Testor, and the way in which those directions can potentially benefit the development of theory and algorithms for solving different practical problems in both areas.",

keywords = "Graph theory, Hitting set, Irreducible testor, Minimal transversal, Testor theory",

author = "Eduardo Alba-Cabrera and Salvador Godoy-Calderon and Lazo-Cortes, {Manuel S.} and {Fco Martinez-Trinidad}, J. and Carrasco-Ochoa, {Jesus A.}",

note = "Publisher Copyright: {\textcopyright} 2013 IEEE.",

year = "2019",

doi = "10.1109/ACCESS.2019.2922231",

language = "Ingl{\'e}s",

volume = "7",

pages = "82809--82816",

journal = "IEEE Access",

issn = "2169-3536",

}

TY - JOUR

T1 - On the Relation between the Concepts of Irreducible Testor and Minimal Transversal

AU - Alba-Cabrera, Eduardo

AU - Godoy-Calderon, Salvador

AU - Lazo-Cortes, Manuel S.

AU - Fco Martinez-Trinidad, J.

AU - Carrasco-Ochoa, Jesus A.

PY - 2019

Y1 - 2019

N2 - This paper aims at studying the relationship between two rather relevant theoretic fields such as Graph Theory and Testor Theory, deepening in the unexploited relation between the concepts of Minimal Transversal and Irreducible Testor. First, the classic definitions of each concept are provided, and then the relation between them is shown and formalized. Some of the immediate consequences of this relation, in terms of the duality property of transversals and about the equivalence of the result of two specific algorithms, one from each field, are discussed. Finally, we also discuss several future research directions that arise from the relationship between the concepts of Minimal Transversal And Irreducible Testor, and the way in which those directions can potentially benefit the development of theory and algorithms for solving different practical problems in both areas.

AB - This paper aims at studying the relationship between two rather relevant theoretic fields such as Graph Theory and Testor Theory, deepening in the unexploited relation between the concepts of Minimal Transversal and Irreducible Testor. First, the classic definitions of each concept are provided, and then the relation between them is shown and formalized. Some of the immediate consequences of this relation, in terms of the duality property of transversals and about the equivalence of the result of two specific algorithms, one from each field, are discussed. Finally, we also discuss several future research directions that arise from the relationship between the concepts of Minimal Transversal And Irreducible Testor, and the way in which those directions can potentially benefit the development of theory and algorithms for solving different practical problems in both areas.

KW - Graph theory

KW - Hitting set

KW - Irreducible testor

KW - Minimal transversal

KW - Testor theory

UR - http://www.scopus.com/inward/record.url?scp=85068859642&partnerID=8YFLogxK

U2 - 10.1109/ACCESS.2019.2922231

DO - 10.1109/ACCESS.2019.2922231

M3 - Artículo

AN - SCOPUS:85068859642

SN - 2169-3536

VL - 7

SP - 82809

EP - 82816

JO - IEEE Access

JF - IEEE Access

M1 - 8735693

ER -

On the Relation between the Concepts of Irreducible Testor and Minimal Transversal

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this