17 citations · 42 across the 15 of their papers we have counts for
9 papers · 1 filter
Space-Efficient Parameterized Algorithms on Graphs of Low Shrubdepth
Benjamin Bergougnoux, Vera Chekan, Robert Ganian +5
Dynamic programming on various graph decompositions is one of the most fundamental techniques used in parameterized complexity. Unfortunately, even if we consider concepts as simpl…
A linear fixed parameter tractable algorithm for connected pathwidth
Mamadou Moustapha Kanté, Christophe Paul, Dimitrios M. Thilikos
The graph parameter of pathwidth can be seen as a measure of the topological resemblance of a graph to a path. A popular definition of pathwidth is given in terms of node search wh…
More applications of the d-neighbor equivalence: acyclicity and connectivity constraints
Benjamin Bergougnoux, Mamadou Moustapha Kanté
In this paper, we design a framework to obtain efficient algorithms for several problems with a global constraint (acyclicity or connectivity) such as Connected Dominating Set, Nod…
An optimal XP algorithm for Hamiltonian cycle on graphs of bounded clique-width
Benjamin Bergougnoux, Mamadou Moustapha Kanté, O-joung Kwon
In this paper, we prove that, given a clique-width -expression of an -vertex graph, \textsc{Hamiltonian Cycle} can be solved in time . This improves the n…
Output-Polynomial Enumeration on Graphs of Bounded (Local) Linear MIM-Width
Petr A. Golovach, Pinar Heggernes, Mamadou Moustapha Kanté +3
The linear induced matching width (LMIM-width) of a graph is a width parameter defined by using the notion of branch-decompositions of a set function on ternary trees. In this pape…
An FPT algorithm and a polynomial kernel for Linear Rankwidth-1 Vertex Deletion
Mamadou Moustapha Kanté, Eun Jung Kim, O-joung Kwon +1
Linear rankwidth is a linearized variant of rankwidth, introduced by Oum and Seymour [Approximating clique-width and branch-width. J. Combin. Theory Ser. B, 96(4):514--528, 2006].…
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…
Compact Labelings For Efficient First-Order Model-Checking
Bruno Courcelle, Cyril Gavoille, Mamadou Moustapha Kanté
We consider graph properties that can be checked from labels, i.e., bit sequences, of logarithmic length attached to vertices. We prove that there exists such a labeling for checki…