33 citations · 48 across the 15 of their papers we have counts for
8 papers · 1 filter
On the hardness of inclusion-wise minimal separators enumeration
Caroline Brosse, Oscar Defrain, Kazuhiro Kurita +3
Enumeration problems are often encountered as key subroutines in the exact computation of graph parameters such as chromatic number, treewidth, or treedepth. In the case of treedep…
Contact graphs of boxes with unidirectional contacts
Daniel Gonçalves, Vincent Limouzy, Pascal Ochem
This paper is devoted to the study of particular geometrically defined intersection classes of graphs. Those were previously studied by Magnant and Martin, who proved that these gr…
On dually-CPT and strong-CPT posets
Liliana Alcón, Martin Charles Golumbic, Noemí Gudiño +2
A poset is a containment of paths in a tree (CPT) if it admits a representation by containment where each element of the poset is represented by a path in a tree and two elements a…
Connected greedy colourings of perfect graphs and other classes: the good, the bad and the ugly
Laurent Beaudou, Caroline Brosse, Oscar Defrain +4
The Grundy number of a graph is the maximum number of colours used by the "First-Fit" greedy colouring algorithm over all vertex orderings. Given a vertex ordering $σ= v_1,\dots,v_…
Efficient enumeration of maximal split subgraphs and induced sub-cographs and related classes
Caroline Brosse, Aurélie Lagoutte, Vincent Limouzy +2
In this paper, we are interested in algorithms that take in input an arbitrary graph , and that enumerate in output all the (inclusion-wise) maximal "subgraphs" of which ful…
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…