17 citations · 42 across the 15 of their papers we have counts for
21 papers
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…
Obstructions for matroids of path-width at most k and graphs of linear rank-width at most k
Mamadou Mostapha Kanté, Eun Jung Kim, O-joung Kwon +1
Every minor-closed class of matroids of bounded branch-width can be characterized by a list of excluded minors, but unlike graphs, this list may need to be infinite in general. How…
Generalisations of Matrix Partitions : Complexity and Obstructions
Alexey Barsukov, Mamadou Moustapha Kanté
A trigraph is a graph where each pair of vertices is labelled either 0 (a non-arc), 1 (an arc) or (both an arc and a non-arc). In a series of papers, Hell and co-authors pr…
Letter graphs and geometric grid classes of permutations
Bogdan Alecu, Robert Ferguson, Mamadou Moustapha Kanté +3
We uncover a connection between two seemingly unrelated notions: lettericity, from structural graph theory, and geometric griddability, from the world of permutation patterns. Both…
Tree pivot-minors and linear rank-width
Konrad K. Dabrowski, François Dross, Jisu Jeong +4
Tree-width and its linear variant path-width play a central role for the graph minor relation. In particular, Robertson and Seymour (1983) proved that for every tree~, the class…
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…
Fast exact algorithms for some connectivity problems parametrized by clique-width
Benjamin Bergougnoux, Mamadou Moustapha Kanté
Given a clique-width -expression of a graph , we provide time algorithms for connectivity constraints on locally checkable properties such as Node-Weighted…
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…
Linear rank-width of distance-hereditary graphs II. Vertex-minor obstructions
Mamadou Moustapha Kanté, O-joung Kwon
In the companion paper [Linear rank-width of distance-hereditary graphs I. A polynomial-time algorithm, Algorithmica 78(1):342--377, 2017], we presented a characterization of the l…
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].…
An Upper Bound on the Size of Obstructions for Bounded Linear Rank-Width
Mamadou Moustapha Kanté, O-joung Kwon
We provide a doubly exponential upper bound in on the size of forbidden pivot-minors for symmetric or skew-symmetric matrices over a fixed finite field of linear r…
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…
Linear rank-width of distance-hereditary graphs I. A polynomial-time algorithm
Isolde Adler, Mamadou Moustapha Kanté, O-joung Kwon
Linear rank-width is a linearized variation of rank-width, and it is deeply related to matroid path-width. In this paper, we show that the linear rank-width of every -vertex dis…
A Note on Graphs of Linear Rank-Width 1
Binh-Minh Bui-Xuan, Mamadou Moustapha Kanté, Vincent Limouzy
We prove that a connected graph has linear rank-width 1 if and only if it is a distance-hereditary graph and its split decomposition tree is a path. An immediate consequence is tha…
Well-Quasi-Ordering of Matrices under Schur Complement and Applications to Directed Graphs
Mamadou Moustapha Kanté
In [Rank-Width and Well-Quasi-Ordering of Skew-Symmetric or Symmetric Matrices, arXiv:1007.3807v1] Oum proved that, for a fixed finite field , any infinite sequence $M_…
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…
The Rank-Width of Edge-Colored Graphs
Mamadou Moustapha Kante, Michael Rao
Clique-width is a complexity measure of directed as well as undirected graphs. Rank-width is an equivalent complexity measure for undirected graphs and has good algorithmic and str…