54 citations · 64 across the 8 of their papers we have counts for
5 papers · 1 filter
Parameterized covering in semi-ladder-free hypergraphs
Sylvain Guillemot
In this article, we study the parameterized complexity of the Set Cover problem restricted to semi-ladder-free hypergraphs, a class defined by Fabianski et al. [Proceedings of STAC…
Alternative polynomial-time algorithm for Bipartite Matching
Sylvain Guillemot
If is a bipartite graph, Hall's theorem \cite{H35} gives a condition for the existence of a matching of covering one side of the bipartition. This theorem admits a well-kno…
Finding small patterns in permutations in linear time
Sylvain Guillemot, Dániel Marx
Given two permutations and , the \textsc{Permutation Pattern} problem asks if is a subpattern of . We show that the problem can be solved in time $2^{O(\ell^2\log \el…
A faster FPT algorithm for Bipartite Contraction
Sylvain Guillemot, Dániel Marx
The \textsc{Bipartite Contraction} problem is to decide, given a graph and a parameter , whether we can can obtain a bipartite graph from by at most edge contraction…
On the (non-)existence of polynomial kernels for Pl-free edge modification problems
Sylvain Guillemot, Christophe Paul, Anthony Perez
Given a graph G = (V,E) and an integer k, an edge modification problem for a graph property P consists in deciding whether there exists a set of edges F of size at most k such that…