Concise representation of hypergraph minimal transversals: Approach and application on the dependency inference problem

M. Nidhal Jelassi; Christine Largeron; Sadok Ben Yahia

doi:10.1109/RCIS.2015.7128905

Concise representation of hypergraph minimal transversals: Approach and application on the dependency inference problem

M. Nidhal Jelassi, Christine Largeron, Sadok Ben Yahia

Publikation: Kapitel i bog/rapport/konference-proceeding › Konferencebidrag i proceedings › Forskning › peer review

Abstract

The problem of extracting the minimal transversals from a hypergraph is known to be particularly difficult. Given that the number of minimal transversals can be exponential even for moderately sized hypergraphs, we propose, in this paper, a concise representation of minimal transversals in order to optimize the computation time and we introduce a new algorithm, called IRRED-ENGINE, which extracts all the minimal transversals from a subset. Experiments carried out on several types of hypergraphs, showed that IRRED-ENGINE obtains very interesting results evaluated through a compactness measure. To illustrate the benefit of our approach, we show how our concise representation can be used to solve the dependency inference problem by computing a concise cover of functional dependencies.

Originalsprog	Engelsk
Titel	IEEE RCIS 2015 - 9th International Conference on Research Challenges in Information Science, Proceedings
Redaktører	Colette Rolland, Dimosthenis Anagnostopoulos, Pericles Loucopoulos, Cesar Gonzales-Perez
Forlag	IEEE Press
Publikationsdato	19. jun. 2015
Udgave	June
Sider	434-444
ISBN (Elektronisk)	9781467366304
DOI	https://doi.org/10.1109/RCIS.2015.7128905
Status	Udgivet - 19. jun. 2015
Udgivet eksternt	Ja
Begivenhed	9th IEEE International Conference on Research Challenges in Information Science, IEEE RCIS 2015 - Athens, Grækenland Varighed: 13. maj 2015 → 15. maj 2015

Konference

Konference	9th IEEE International Conference on Research Challenges in Information Science, IEEE RCIS 2015
Land/Område	Grækenland
By	Athens
Periode	13/05/2015 → 15/05/2015

Navn	Proceedings of the International Conference on Research Challenges in Information Science
Nummer	June
Vol/bind	2015-June
ISSN	2151-1349

Bibliografisk note

Publisher Copyright:
© 2015 IEEE.

Dokumenter og links

10.1109/RCIS.2015.7128905

SDU link

Tjek adgangen til materialet i Syddansk Universitetsbiblioteks søgemaskine

Citationsformater

Jelassi, M. N., Largeron, C., & Ben Yahia, S. (2015). Concise representation of hypergraph minimal transversals: Approach and application on the dependency inference problem. I C. Rolland, D. Anagnostopoulos, P. Loucopoulos, & C. Gonzales-Perez (red.), IEEE RCIS 2015 - 9th International Conference on Research Challenges in Information Science, Proceedings (June udg., s. 434-444). IEEE Press. https://doi.org/10.1109/RCIS.2015.7128905

Jelassi, M. Nidhal ; Largeron, Christine ; Ben Yahia, Sadok. / Concise representation of hypergraph minimal transversals : Approach and application on the dependency inference problem. IEEE RCIS 2015 - 9th International Conference on Research Challenges in Information Science, Proceedings. red. / Colette Rolland ; Dimosthenis Anagnostopoulos ; Pericles Loucopoulos ; Cesar Gonzales-Perez. June. udg. IEEE Press, 2015. s. 434-444 (Proceedings of the International Conference on Research Challenges in Information Science; Nr. June, Bind 2015-June).

@inproceedings{d3c08b35a9f149fc811fb905cd3c5c03,

title = "Concise representation of hypergraph minimal transversals: Approach and application on the dependency inference problem",

abstract = "The problem of extracting the minimal transversals from a hypergraph is known to be particularly difficult. Given that the number of minimal transversals can be exponential even for moderately sized hypergraphs, we propose, in this paper, a concise representation of minimal transversals in order to optimize the computation time and we introduce a new algorithm, called IRRED-ENGINE, which extracts all the minimal transversals from a subset. Experiments carried out on several types of hypergraphs, showed that IRRED-ENGINE obtains very interesting results evaluated through a compactness measure. To illustrate the benefit of our approach, we show how our concise representation can be used to solve the dependency inference problem by computing a concise cover of functional dependencies.",

author = "Jelassi, \{M. Nidhal\} and Christine Largeron and \{Ben Yahia\}, Sadok",

note = "Publisher Copyright: {\textcopyright} 2015 IEEE.; 9th IEEE International Conference on Research Challenges in Information Science, IEEE RCIS 2015 ; Conference date: 13-05-2015 Through 15-05-2015",

year = "2015",

month = jun,

day = "19",

doi = "10.1109/RCIS.2015.7128905",

language = "English",

series = "Proceedings of the International Conference on Research Challenges in Information Science",

publisher = "IEEE Press",

number = "June",

pages = "434--444",

editor = "Colette Rolland and Dimosthenis Anagnostopoulos and Pericles Loucopoulos and Cesar Gonzales-Perez",

booktitle = "IEEE RCIS 2015 - 9th International Conference on Research Challenges in Information Science, Proceedings",

edition = "June",

}

Jelassi, MN, Largeron, C & Ben Yahia, S 2015, Concise representation of hypergraph minimal transversals: Approach and application on the dependency inference problem. i C Rolland, D Anagnostopoulos, P Loucopoulos & C Gonzales-Perez (red), IEEE RCIS 2015 - 9th International Conference on Research Challenges in Information Science, Proceedings. June udg, IEEE Press, Proceedings of the International Conference on Research Challenges in Information Science, nr. June, bind 2015-June, s. 434-444, 9th IEEE International Conference on Research Challenges in Information Science, IEEE RCIS 2015, Athens, Grækenland, 13/05/2015. https://doi.org/10.1109/RCIS.2015.7128905

Concise representation of hypergraph minimal transversals: Approach and application on the dependency inference problem. / Jelassi, M. Nidhal; Largeron, Christine; Ben Yahia, Sadok.
IEEE RCIS 2015 - 9th International Conference on Research Challenges in Information Science, Proceedings. red. / Colette Rolland; Dimosthenis Anagnostopoulos; Pericles Loucopoulos; Cesar Gonzales-Perez. June. udg. IEEE Press, 2015. s. 434-444 (Proceedings of the International Conference on Research Challenges in Information Science; Nr. June, Bind 2015-June).

Publikation: Kapitel i bog/rapport/konference-proceeding › Konferencebidrag i proceedings › Forskning › peer review

TY - GEN

T1 - Concise representation of hypergraph minimal transversals

T2 - 9th IEEE International Conference on Research Challenges in Information Science, IEEE RCIS 2015

AU - Jelassi, M. Nidhal

AU - Largeron, Christine

AU - Ben Yahia, Sadok

PY - 2015/6/19

Y1 - 2015/6/19

N2 - The problem of extracting the minimal transversals from a hypergraph is known to be particularly difficult. Given that the number of minimal transversals can be exponential even for moderately sized hypergraphs, we propose, in this paper, a concise representation of minimal transversals in order to optimize the computation time and we introduce a new algorithm, called IRRED-ENGINE, which extracts all the minimal transversals from a subset. Experiments carried out on several types of hypergraphs, showed that IRRED-ENGINE obtains very interesting results evaluated through a compactness measure. To illustrate the benefit of our approach, we show how our concise representation can be used to solve the dependency inference problem by computing a concise cover of functional dependencies.

AB - The problem of extracting the minimal transversals from a hypergraph is known to be particularly difficult. Given that the number of minimal transversals can be exponential even for moderately sized hypergraphs, we propose, in this paper, a concise representation of minimal transversals in order to optimize the computation time and we introduce a new algorithm, called IRRED-ENGINE, which extracts all the minimal transversals from a subset. Experiments carried out on several types of hypergraphs, showed that IRRED-ENGINE obtains very interesting results evaluated through a compactness measure. To illustrate the benefit of our approach, we show how our concise representation can be used to solve the dependency inference problem by computing a concise cover of functional dependencies.

U2 - 10.1109/RCIS.2015.7128905

DO - 10.1109/RCIS.2015.7128905

M3 - Article in proceedings

AN - SCOPUS:84937864193

T3 - Proceedings of the International Conference on Research Challenges in Information Science

SP - 434

EP - 444

BT - IEEE RCIS 2015 - 9th International Conference on Research Challenges in Information Science, Proceedings

A2 - Rolland, Colette

A2 - Anagnostopoulos, Dimosthenis

A2 - Loucopoulos, Pericles

A2 - Gonzales-Perez, Cesar

PB - IEEE Press

Y2 - 13 May 2015 through 15 May 2015

ER -

Jelassi MN, Largeron C, Ben Yahia S. Concise representation of hypergraph minimal transversals: Approach and application on the dependency inference problem. I Rolland C, Anagnostopoulos D, Loucopoulos P, Gonzales-Perez C, red., IEEE RCIS 2015 - 9th International Conference on Research Challenges in Information Science, Proceedings. June udg. IEEE Press. 2015. s. 434-444. (Proceedings of the International Conference on Research Challenges in Information Science; Nr. June, Bind 2015-June). doi: 10.1109/RCIS.2015.7128905

Concise representation of hypergraph minimal transversals: Approach and application on the dependency inference problem

Abstract

Konference

Bibliografisk note

Dokumenter og links

SDU link

Fingeraftryk

Citationsformater