Author name cluster

Sylvain Guillemot

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers

2 author rows

SODA Conference 2014 Conference Paper

Finding small patterns in permutations in linear time

Sylvain Guillemot
Dániel Marx

Given two permutations σ and π, the P ermutation P attern problem asks if σ is a subpattern of π. We show that the problem can be solved in time 2 O ( ℓ 2 log ℓ ). n, where ℓ = | σ | and n = | π |. In other words, the problem is fixed-parameter tractable parameterized by the size of the subpattern to be found. We introduce a novel type of decompositions for permutations and a corresponding width measure. We present a linear-time algorithm that either finds σ as a subpattern of π, or finds a decomposition of π whose width is bounded by a function of | σ |. Then we show how to solve the P ermutation P attern problem in linear time if a bounded-width decomposition is given in the input.

Details

TCS Journal 2013 Journal Article

Kernel and fast algorithm for dense triplet inconsistency

Sylvain Guillemot
Matthias Mnich

We study the parameterized complexity of inferring supertrees from sets of rooted triplets, an important problem in phylogenetics. For a set L of labels and a dense set T of triplets distinctly leaf-labeled by 3-subsets of L, we seek a tree distinctly leaf-labeled by L and containing all but at most k triplets from T as homeomorphic subtree. Our results are the first polynomial kernel for this problem, with O ( k 2 ) labels, and a subexponential fixed-parameter algorithm running in time O ( ∣ L ∣ 4 ) + 2 O ( k 1 / 3 log k ).

Details DOI

MFCS Conference 2010 Conference Paper

Finding and Counting Vertex-Colored Subtrees

Sylvain Guillemot
Florian Sikora

Abstract The problems studied in this article originate from the Graph Motif problem introduced by Lacroix et al. [17] in the context of biological networks. The problem is to decide if a vertex-colored graph has a connected subgraph whose colors equal a given multiset of colors M. Using an algebraic framework recently introduced by Koutis et al. [15, 16], we obtain new FPT algorithms for Graph Motif and variants, with improved running times. We also obtain results on the counting versions of this problem, showing that the counting problem is FPT if M is a set, but becomes # W [1] -hard if M is a multiset with two colors.

Details