Detecting $K_{2,3}$ as an induced minor

Autor: Dallard, Clément, Dumas, Maël, Hilaire, Claire, Milanič, Martin, Perez, Anthony, Trotignon, Nicolas

We consider a natural generalization of chordal graphs, in which every minimal separator induces a subgraph with independence number at most $2$. Such graphs can be equivalently defined as graphs that do not contain the complete bipartite graph $K_{2

Externí odkaz: http://arxiv.org/abs/2402.08332

On graphs coverable by k shortest paths

Autor: Dumas, Maël, Foucaud, Florent, Perez, Anthony, Todinca, Ioan

We show that if the edges or vertices of an undirected graph $G$ can be covered by $k$ shortest paths, then the pathwidth of $G$ is upper-bounded by a single-exponential function of $k$. As a corollary, we prove that the problem Isometric Path Cover

Externí odkaz: http://arxiv.org/abs/2206.15088

A cubic vertex-kernel for Trivially Perfect Editing

Autor: Dumas, Maël, Perez, Anthony, Todinca, Ioan

We consider the Trivially Perfect Editing problem, where one is given an undirected graph $G = (V,E)$ and a parameter $k \in \mathbb{N}$ and seeks to edit (add or delete) at most $k$ edges from $G$ to obtain a trivially perfect graph. The related Tri

Externí odkaz: http://arxiv.org/abs/2105.08549

Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.

Polynomial Kernels for Strictly Chordal Edge Modification Problems

Autor: Dumas, Maël, Perez, Anthony, Todinca, Ioan

Publikováno v: 16th International Symposium on Parameterized and Exact Computation, IPEC
16th International Symposium on Parameterized and Exact Computation, IPEC, Sep 2021, Lisbonne (online), Portugal. pp.17:1--17:16

We consider the Strictly Chordal Editing problem, where one is given an undirected graph G = (V,E) and a parameter k ��� ��� and seeks to edit (add or delete) at most k edges from G to obtain a strictly chordal graph. Problems Strictly Ch

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::50ef5b9401b4f542efefeb8b6ad67a19
https://hal.archives-ouvertes.fr/hal-03483395