Research

Main interests are:

• Structural decompositions and associated width measures, mainly those based on branch-decomposition of symmetric submodular functions (branch-width, rank-width, etc.) We seek for understanding the structure or having fast algorithms using the width measures.
• Listing problems such as the Hypergraph transversal problem or the listing of subgraphs satisfying some properties.
• Convexity problems in graphs, and mainly from the computation side.
• More recently, expressions of graph decompositions in (dynamic) logic.

Conference Proceedings editor

• 40th International Symposium on Theoretical Aspects of Computer Science, STACS 2023, March 7-9, 2023, Hamburg, Germany
  P. Berenbrink, P. Bouyer, A. Dawar and M. M. Kanté
  * LIPICS (2023)
  
  
• 41st International Symposium on Theoretical Aspects of Computer Science, STACS 2024, March 12-14, 2024, Clermont-Ferrand, France
  Olaf Beyersdorff, M. M., Kanté, O. Kupferman and D. Lokshtanov
  * LIPICS (2024)
  
  

Papers

• Elementary FO-model Cheking : Find out where the flaw is (pdf)
  Anonymous
  * Flawed proof, 2024
  
  
• On the Definability of some Tree-width 2 graphs in Dyn-FO (pdf)
  B. Guillon, M. M. Kanté and J. Taheri
  * In preparation, 2024
  
  
• MSO-definability of Canonical Decompositions (pdf)
  et al.
  * In preparation, 2024
  
  
• Definable Decompositions for Finitely Representable Matroids of Bounded Path-Width (pdf)
  et al.
  * In preparation, 2024
  
  
• Lettericity of graphs : an FPT algorithm and a bound on the size of obstructions (pdf)
  B. Alecu, M.M. Kanté, V. Lozin and V. Zamaraev
  * Submitted, 2024
  
  
• Listing Maximal H-free Graphs (pdf)
  A. Conte, R. Grossi, M.M. Kanté, A. Marino and T. Uno
  * revised version submitted 2024
  
  
• Generalisations of matrix partitions: Complexity and obstructions. (pdf)
  A. Barsukov and M.M. Kanté
  * Theoretical Computer Science (2024)
  
  
• Space-Efficient Parameterized Algorithms on Graphs of Low Shrubdepth (pdf)
  M.M. Kanté, E-J. Kim, O-J. Kwon and S. Oum
  * Extended Abstract in ESA 2023
  * Journal version in preparation, 2024
  
  
• Obstructions for Matroids of Path-Width at most k and Graphs of Linear Rank-Width at most k (pdf)
  M.M. Kanté, E-J. Kim, O-J. Kwon and S. Oum
  * Extended Abstract in STACS 2022
  * JCTB (2023)
  
  
• A Linear Fixed Parameter Tractable Algorithm for Connected Pathwidth (pdf)
  M.M. Kanté, C. Paul and D. Thilikos
  * Extended Abstract in ESA 2020
  * SIDMA (2022)
  
  
• Letter Graphs and Geometric Grid Classes of Permutations (pdf)
  B. Alecu, R. Ferguson, M.M. Kanté, V. Lozin, V. Vatter and V. Zamaraev
  * SIDMA (2022)
  
  
• Between clique-width and linear clique-width of bipartite graphs (pdf)
  B. Alecu, M.M. Kanté, V. Lozin and V. Zamaraev
  * Discrete Mathematics (2020)
  
  
• Efficient Enumeration of Maximal Subgraphs with Bounded Girth
  A. Conte, M.M. Kanté, K. Kurita, K. Wasa and T. Uno
  * In preparation 2020
  
  
• More Applications of the $d$-neighbor equivalence: Connectivity and Acyclicity Constraints (pdf)
  B. Bergougnoux and M.M. Kanté
  * Extended Abstract in ESA 2019
  * SIDMA (2021)
  
  
• On the parameterized complexity of the geodesic hull number (pdf)
  M.M. Kanté, T. Marcilon and R. Sampaio
  * Theoretical Computer Science (2019)
  
  
• Listing Induced Steiner Subgraphs as a Compact Way to Discover Steiner Trees in Graphs (pdf)
  A. Conte, R. Grossi, M.M. Kanté, A. Marino, T. Uno and K. Wasa
  * MFCS 2019
  * Journal version in preparation 2019
  
  
• Maximal Irredundant Set Enumeration in Bounded-Degeneracy and Bounded-Degree Hypergraphs (pdf)
  A. Conte, M.M. Kanté, A. Marino and T. Uno
  * IWOCA 2019
  
  
• Tree Pivot-Minors and Linear Rank-Width (pdf)
  K. Dabrowski, F. Dross, J. Jeong, M.M. Kanté, O-J. Kwon, S. Oum, D. Paulusma
  * EuroComb 2019
  * SIDMA (2021)
  
  
• Counting Minimal Transversals in beta-acyclic Hypergraphs (pdf)
  B. Bergougnoux, F. Capelli, M.M. Kanté
  * Journal of Computer and System Sciences (2019)
  
  
• Fast Exact Algorithms for some Connectivity Problems Parametrized by Clique-Width (pdf)
  B. Bergougnoux and M.M. Kanté
  * Theoretical Computer Science (2019)
  
  
• Enumerating Minimal Transversals of Hypergraphs without Small Holes (pdf)
  Mamadou Moustapha Kanté, Kaveh Khoshkhah, Mozhgan Pourmoradnasseri:
  * Extended Abstract in MFCS 2018
  
  
• Computing Small Pivot-Minors
  K. Dabrowski, F. Dross, J. Jeong, M.M. Kanté, O-J. Kwon, S. Oum, D. Paulusma
  * Extended Abstract in WG 2018
  * Journal version submitted, 2024
  
  
• Linear Rank-Width of Distance-Hereditary Graphs II. Vertex-Minor Obstructions (pdf)
  M.M. Kanté and O. Kwon
  * European Journal of Combinatorics (2018)
  
  
• On Maximal Cliques with Connectivity Constraints in Directed Graphs
  A. Conte, M.M. Kanté, T. Uno and K. Wasa
  * Extended Abstract in ISAAC 2017
  * Discrete Applied Mathematics 2020
  
  
• Efficient Enumeration of Maximal k-Degenerate Subgraphs in a Chordal Graph
  A. Conte, M.M. Kanté, Y. Otachi, T. Uno and K. Wasa
  * Extended Abstract in COCOON 2017
  * Theoretical Computer Science (2018)
  
  
• An Optimal XP Algorithm for Hamiltonian Cycle on Graphs of Bounded Clique-Width (pdf)
  B. Bergougnoux, M.M. Kanté and O-J. Kwon
  * Extended Abstract in WADS 2017
  * Algorithmica (2020)
  
  
• Counting Minimal Dominating Sets (pdf)
  M.M. Kanté and T. Uno
  * Extended Abstract in TAMC 2017
  
  
• Linear Rank-Width of Distance-Hereditary Graphs I. A Polynomial-Time Algorithm (pdf)
  I. Adler, M.M. Kanté and O. Kwon
  * Algorithmica (2017)
  
  
• FPT Algorithm and Polynomial Kernel for Linear Rank-width One Vertex Deletion (pdf)
  M.M. Kanté, E.J. kim, O. Kwon and C. Paul
  * Extended Abstract in IPEC 2015 (LIPICS 43, pages 138--150)
  * Algorithmica (2017)
  
  
• On the Geodetic Rank of a Graph (pdf)
  M.M. Kanté, R.M. Sampaio, V.F. Dos Santos and J.L. Szwarcfiter
  * Journal of Combinatorics (2016)
  
  
• Output-Polynomial Enumeration Algorithms for Graphs of Bounded Linear Induced Matching Width (pdf)
  P.A. Golovach, P. Heggernes, M.M. Kanté, D. Kratsch, S.H. Saether and Y. Villanger
  * Extended Abstract in ISAAC 2015 (LNCS 9472, pages 248--258)
  * Algorithmica (2018)
  
  
• Polynomial Delay Algorithm for Listing Minimal Edge Dominating Sets in Graphs (pdf)
  M.M. Kanté, A. Mary, V. Limouzy, L. Nourine and T. Uno
  * Extended Abstract in WADS 2015 (LNCS 9214, pages 446--457)
  
  
• A Polynomial Delay Algorithm for Enumerating Minimal Dominating Sets in Chordal Graphs (pdf)
  M.M. Kanté, A. Mary, V. Limouzy, L. Nourine and T. Uno
  * Extended Abstract in WG 2015 (LNCS 9224, pages 138--153)
  
  
• Finding Paths in Grids with Forbidden Transitions (pdf)
  M.M. Kanté, F.Z. Moataz, B. Momège, N. Nisse
  * Workshop ALGOTEL 2015
  * Extended Abstract in WG 2015 (LNCS 9224, pages 154--168)
  
  
• Enumerating Minimal Dominating Sets in Chordal Bipartite Graphs (pdf)
  P.A. Golovach, P. Heggernes, M.M. Kanté, D. Kratsch and Y. Villanger
  * Discrete Applied Mathematics, 199:30--36 (2015)
  
  
• Minimal Dominating Set Enumeration (pdf)
  M.M. Kanté, and L. Nourine
  * Encyclopedia of Algorithms, pages 1--5, 2014
  
  
• Minimal Dominating Sets in Interval Graphs and Trees (pdf)
  P.A. Golovach, P.Heggernes, M.M. Kanté, D. Kratsch and Y. Villanger
  * Discrete Applied Mathematics (2016)
  
  
• Linear Rank-Width of Distance-Hereditary Graphs (pdf)
  I. Adler, M.M. Kanté and O. Kwon
  * Extended abstract in WG 2014 (LNCS 8747, pages 42--55)
  * Full version in two separate papers
  
  
• On the Enumeration of Minimal Dominating Sets and Related Notions (pdf)
  M.M. Kanté, A. Mary, V. Limouzy and L. Nourine
  * Extended Abstract in FCT 2011 (LNCS 6914, pages 298--309)
  * SIAM J. Discrete Math. 28(4):1916--1929 (2014)
  
  
• On the Enumeration and Counting of Minimal Dominating Sets in Interval and Permutation Graphs (pdf)
  M.M. Kanté, A. Mary, V. Limouzy, L. Nourine and T. Uno
  * Extended Abstract in ISAAC 2013 (LNCS 8283, pages 339--349)
  
  
• Linear Rank-Width and Linear Clique-Width of Trees (pdf)
  I. Adler and M.M. Kanté
  * Extended Abstract in WG 2013 (LNCS 8283, pages 339--349)
  * Theor. Comput. Sci. 589: 87--98 (2015)
  
  
• Polynomial Time Algorithms for Computing a Minimum Hull Set in Distance-Hereditary and Chordal Graphs (Algorithm on chordal graphs withdrawn)
  M.M. Kanté and L. Nourine
  * Extended Abstract in SOFSEM 2013 (LNCS 7741, pages 268--279)
  * SIAM J. Discrete Math. 30(1):311--326 (2016)
  
  
• An Exact Algorithm to Check the Existence of (Elementary) Paths and a Generalisation of the Cut Problem in Graphs with Forbidden Transitions (pdf)
  M.M. Kanté, C. Laforest and B. Momège
  * Extended Abstract in SOFSEM 2013 (LNCS 7741, pages 257--267)
  
  
• Trees in Graphs with Conflict Edges or Forbidden Transitions (pdf)
  M.M. Kanté, C. Laforest and B. Momège
  * Extended Abstract in TAMC 2013 (LNCS 7876, pages 343--354)
  
  
• The Rank-Width of Edge-Coloured Graphs (pdf)
  M.M. Kanté and M. Rao
  * Extended Abstract in CAI 2011 (LNCS 6742, pages 158--173)
  * Theory of Computing Systems, 52(4):599--644 (2013)
  
  
• A Note on Graphs of Linear Rank-Width 1 (pdf)
  B.M. Bui-Xuan, M.M. Kanté and V. Limouzy
  * Manuscript, 2013
  
  
• On the Neighbourhood Helly of some Graph Classes and Applications to the Enumeration of Minimal Dominating Sets (pdf)
  M.M. Kanté, A. Mary, V. Limouzy and L. Nourine
  * Extended Abstract in ISAAC 2012 (LNCS 7676, pages 289--298)
  
  
• The Lattice of all Betweenness Relations : Structure and Properties
  L. Beaudou, M.M. Kanté, and L. Nourine
  * Extended Abstract in CLA 2012 (CEUR 972, pages 317--326)
  
  
• Well-Quasi-Ordering of Matrices under Schur Complement and Applications to Directed Graphs (pdf)
  M.M. Kanté
  * European Journal of Combinatorics, 33(8):1820--1841 (2012)
  
  
• Optimal Labeling for Connectivity Checking in Planar Networks with Obstacles I: 3-Connected and Bounded Degree Networks (pdf)
  B. Courcelle, C. Gavoille, M.M. Kanté and A. Twigg
  * Extended Abstract in TGGT 2008 (ENDM 31, pages 151--155)
  * Manuscript, 2011
  
  
• Optimal Labeling for Connectivity Checking in Planar Networks with Obstacles II: The General Case (pdf)
  B. Courcelle, C. Gavoille, M.M. Kanté and A. Twigg
  * Manuscript, 2011
  
  
• Directed Rank-Width and Displit Decomposition (pdf)
  M.M. Kanté and M. Rao
  * Extended Abstract in WG 2009 (LNCS 5911, pages 214--225)
  
  
• Compact Labelings for Efficient First-Order Model-Checking (pdf)
  B. Courcelle, C. Gavoille and M.M. Kanté
  * Extended Abstract in FAW 2008 (LNCS 5059, pages 159--170)
  * Journal of Combinatorial Optimization, 21(1):19--46 (2011)
  
  
• Short Labeling Scheme for Connectivity Check on Certain Graph Classes of Unbounded Clique-Width (pdf)
  M.M. Kanté
  * DIMAP Workshop on Algorithmic Graph Theory.
  
  
• Graph Operations Characterizing Rank-Width (pdf)
  B. Courcelle and M.M. Kanté
  * Extended Abstract in WG 2007 (LNCS 4769, pages 66--75)
  * Discrete Applied Mathematics, 157(4):627--640 (2009)
  
  
• Balanced Graph Expressions (pdf)
  B. Courcelle and M.M. Kanté
  * Extended Abstract in WG 2007 (LNCS 4769, pages 66--75)
  * Manuscript, 2010
  
  
• The Rank-Width of Directed Graphs (pdf)
  M.M. Kanté
  * Manuscript, 2008.
  
  
• Forbidden-Set Labeling Schemes on Graphs (pdf)
  B. Courcelle, C. Gavoille, M.M. Kanté and A.D. Twigg
  * Workshop on Locality Preserving Distributed Computing Methods (LOCALITY), August 2007. Co-located with PODC 2007.
  
  
• Vertex-Minor Reductions can Simulate Edge Contractions (pdf)
  M.M. Kanté
  * Discrete Applied Mathematics, 155(17):2328-2340 (2007)
  
  

Thesis

• Habilitation
  * Université Blaise Pascal, 2015
  
  
• PhD thesis
  * Université Bordeaux 1, 2008
  
  

Talks

• Université de Caen (Algorithmic group, GREYC Feb 05, 2019) Enumeration Problems : the Hypergraph Dualisation Problem (pdf)
  
• NII (Seminar Nov 03, 2018) Enumeration Problems : the Hypergraph Dualisation Problem (pdf)
  
• MFCS (43^rdMathematical Foundations of Computer Science August 30, 2018) Enumerating Minimal Transversals of Hypergraphs without Small Holes (pdf)
  
• Bergen's Algorithm Seminar (Seminar June 15^th, 2017) Connected Domination Problems Parametrised by Clique-Width (pdf)
  
• Logic and Semantic's Research Group (Seminar February 1^st, 2017) Singly exponential time algorithms for some connectivity problems parameterized by clique-width (pdf)
  
• LORENTZ INSTITUTE (Leiden) (Workshop on Enumeration Algorithms Using Structure August 26, 2015) Intertaction between Input and Output-Sensitive (Really?) (pdf)
  
• FUC (Fortaleza, Brazil) (Seminar October 23^rd, 2015) Output-Polynomial Time Algorithms: The Cases of Minimal Dominating Sets and Transversals (pdf)
  
• UFRJ (Rio de Janeiro, Brazil) (Seminar October 21^st, 2015) Output-Polynomial Time Algorithms: The Cases of Minimal Dominating Sets and Transversals (pdf)
  
• CIRM (Marseille) (Workshop on Graph Decompositions January 22^nd, 2015) An Upper Bound on the Size of Obstructions for Linear Rank-Width (pdf)
  
• KAIST University (Discrete Math Seminar October 28, 2014) On the Enumeration of Minimal Transversals in Hypergraphs (on blackboard)
  
• Université de Marseille (ACRO Workgroup, LIF May 26, 2014) On the Lattice Structure of Betweenness Relations and the Particular Case of the Geodesic One (pdf)
  
• Université de Paris Sorbonne (Seminar of Discrete Mathematics, Optimisation and Decision November 19, 2013) On the Lattice Structure of Betweenness Relations and the Particular Case of the Geodesic One (pdf)
  
• GROW (Santorini Island, University of Athens) (6^th Workshop on Graph Classes, Optimisation and Width Parameters October 19, 2013) On the linear rank-width of trees (pdf)
  
• WG (39^th International Workshop on Graph-Theoretic Concepts in Computer Science June 19, 2013) Linear Rank-Width and Linear Clique-Width of Trees (pdf)
  
• University of Bergen (Algorithm Group May 10, 2013) Linear Rank-Width and Linear Clique-Width of Trees