33 citations · 48 across the 15 of their papers we have counts for
12 papers · 1 filter
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…
Polynomial delay algorithm for minimal chordal completions
Caroline Brosse, Vincent Limouzy, Arnaud Mary
Motivated by the problem of enumerating all tree decompositions of a graph, we consider in this article the problem of listing all the minimal chordal completions of a graph. In \c…
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…