3 citations · 4 across the 13 of their papers we have counts for
18 papers
Characterizing the optimum bases of a convex geometry using quasi-closed hypergraphs
Anthony Meunier, Lhouari Nourine, Simon Vilmin
Optimizing an implicational base of a closure system consists in turning this implicational base into an equivalent one with premises and conclusions as small as possible. This tas…
Half-space separation in monophonic convexity
Mohammed Elaroussi, Lhouari Nourine, Simon Vilmin
We study half-space separation in the convexity of chordless paths of a graph, i.e., monophonic convexity. In this problem, one is given a graph and two (disjoint) subsets of verti…
Computing the -base and -relation in finite closure systems
Kira Adaricheva, Lhouari Nourine, Simon Vilmin
Implicational bases (IBs) are a common representation of finite closure systems and lattices, along with meet-irreducible elements. They appear in a wide variety of fields ranging…
Complexity of conjunctive regular path query homomorphisms
Laurent Beaudou, Florent Foucaud, Florent R. Madelaine +3
A graph database is a digraph whose arcs are labeled with symbols from a fixed alphabet. A regular graph pattern (RGP) is a digraph whose arcs are labeled with regular expressions…
Hierarchical decompositions of implicational bases for the enumeration of meet-irreducible elements
Lhouari Nourine, Simon Vilmin
We are interested in the problem of translating between two representations of closure systems, namely implicational bases and meet-irreducible elements. Albeit its importance, the…
On the preferred extensions of argumentation frameworks: bijections with naive sets
Mohammed Elaroussi, Lhouari Nourine, Mohammed Said Radjef +1
This paper deals with the problem of finding the preferred extensions of an argumentation framework by means of a bijection with the naive sets of another framework. First, we cons…
Enumerating maximal consistent closed sets in closure systems
Lhouari Nourine, Simon Vilmin
Given an implicational base, a well-known representation for a closure system, an inconsistency binary relation over a finite set, we are interested in the problem of enumerating a…
Hierarchical Decompositions of dihypergraphs
Lhouari Nourine, Simon Vilmin
In this paper we are interested in decomposing a dihypergraph into simpler dihypergraphs, that can be handled more efficiently. We study the proper…
Enumerating minimal dominating sets in the (in)comparability graphs of bounded dimension posets
Marthe Bonamy, Oscar Defrain, Piotr Micek +1
Enumerating minimal transversals in a hypergraph is a notoriously hard problem. It can be reduced to enumerating minimal dominating sets in a graph, in fact even to enumerating min…
Representations for the largest Extension of a closure system
Karima Ennaoui, Khaled Maafa, Lhouari Nourine
We consider extension of a closure system on a finite set S as a closure system on the same set S containing the given one as a sublattice. A closure system can be represented in d…
Towards declarative comparabilities: application to functional dependencies
Lhouari Nourine, Jean Marc Petit, Simon Vilmin
In real life, data are often of poor quality as a result, for instance, of uncertainty, mismeasurements, missing values or bad inputs. This issue hampers an implicit yet crucial op…
Translating between the representations of a ranked convex geometry
Oscar Defrain, Lhouari Nourine, Simon Vilmin
It is well known that every closure system can be represented by an implicational base, or by the set of its meet-irreducible elements. In Horn logic, these are respectively known…
On the dualization in distributive lattices and related problems
Oscar Defrain, Lhouari Nourine, Takeaki Uno
In this paper, we study the dualization in distributive lattices, a generalization of the well-known hypergraph dualization problem. We in particular propose equivalent formulation…
Dualization in lattices given by implicational bases
Oscar Defrain, Lhouari Nourine
It was recently proved that the dualization in lattices given by implicational bases is impossible in output-polynomial time unless P=NP. In this paper, we~show that this result ho…
Neighborhood inclusions for minimal dominating sets enumeration: linear and polynomial delay algorithms in -free and -free chordal graphs
Oscar Defrain, Lhouari Nourine
In [M. M. Kanté, V. Limouzy, A. Mary, and L. Nourine. On the enumeration of minimal dominating sets and related notions. SIAM Journal on Discrete Mathematics, 28(4):1916-1929, 2014…
On the Enumeration of Minimal Dominating Sets and Related Notions
Mamadou Moustapha Kanté, Vincent Limouzy, Arnaud Mary +1
A dominating set in a graph is a subset of its vertex set such that each vertex is either in or has a neighbour in . In this paper, we are interested in the enumeration…
A Polynomial Delay Algorithm for Enumerating Minimal Dominating Sets in Chordal Graphs
Mamadou Moustapha Kanté, Vincent Limouzy, Arnaud Mary +2
An output-polynomial algorithm for the listing of minimal dominating sets in graphs is a challenging open problem and is known to be equivalent to the well-known Transversal proble…
Polynomial Delay Algorithm for Listing Minimal Edge Dominating sets in Graphs
Mamadou Moustapha Kanté, Vincent Limouzy, Arnaud Mary +2
The Transversal problem, i.e, the enumeration of all the minimal transversals of a hypergraph in output-polynomial time, i.e, in time polynomial in its size and the cumulated size…