33 citations · 48 across the 15 of their papers we have counts for
22 papers
Output-linear time enumeration of potential maximal cliques
Pierre Bergé, Vincent Limouzy, Nicolas Schivre
First defined by Bouchitté and Todinca, Potential Maximal Cliques (PMC) are a well studied notion in graph theory due to its numerous applications. The PMCs of an undirected graph…
The Canadian Traveller Problem on outerplanar graphs
Laurent Beaudou, Pierre Bergé, Vsevolod Chernyshev +5
We study the -Canadian Traveller Problem, where a weighted graph with a source and a target are given. This problem also has a hidden input $E_* \s…
Output-Sensitive Enumeration of Potential Maximal Cliques in Polynomial Space
Caroline Brosse, Alessio Conte, Vincent Limouzy +2
A set of vertices in a graph forms a potential maximal clique if there exists a minimal chordal completion in which it is a maximal clique. Potential maximal cliques were first int…
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…