Výsledky vyhledávání - "Kant��, Mamadou Moustapha"

Obstructions for matroids of path-width at most k and graphs of linear rank-width at most k

Autor: Kant��, Mamadou Moustapha, Kim, Eun Jung, Kwon, O-joung, Oum, Sang-il

Publikováno v: Journal of Combinatorial Theory, Series B
Journal of Combinatorial Theory, Series B, 2023, 160, pp.15-35. ⟨10.1016/j.jctb.2022.12.004⟩
STACS 2022
STACS 2022, Mar 2022, Marseille, France

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. However, for each fixed finite field $\mathbb F$, the list needs to conta

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::36a29e4afcb665b3319009bf0dd6c289
http://arxiv.org/abs/2109.12291

Zobrazit plný text záznamu

Counting Minimal Transversals of $��$-Acyclic Hypergraphs

Autor: Bergougnoux, Benjamin, Capelli, Florent, Kant��, Mamadou Moustapha

We prove that one can count in polynomial time the number of minimal transversals of $��$-acyclic hypergraphs. In consequence, we can count in polynomial time the number of minimal dominating sets of strongly chordal graphs, continuing the line o

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::5fbdd7021bdc73cdf6dfa902dbda6d33

Zobrazit plný text záznamu

A Polynomial Delay Algorithm for Enumerating Minimal Dominating Sets in Chordal Graphs

Autor: Kant��, Mamadou Moustapha, Limouzy, Vincent, Mary, Arnaud, Nourine, Lhouari, Uno, Takeaki

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 problem which asks for an output-polynomial algorithm for listing the set of

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::1fa05b3832397d6fdc4eba3443a3c6ca
http://arxiv.org/abs/1407.2036

Zobrazit plný text záznamu

A Note on Graphs of Linear Rank-Width 1

Autor: Bui-Xuan, Binh-Minh, Kant��, Mamadou Moustapha, Limouzy, Vincent

Publikováno v: CoRR
CoRR, 2013, abs/1306.1345

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 that one can decide in linear time whether a graph has linear rank-width

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::874046ed55d3d60d76301f07ab279d64
https://hal.archives-ouvertes.fr/hal-02083532

Zobrazit plný text záznamu

Vyhledávací nástroje:

Upřesnit hledání