Stéphan Thomassé

activity

20062023

most citedThe Domination Number of Grids

115 citations · 430 across the 53 of their papers we have counts for

collaborators

Showing 2010Show all

2 papers · 1 filter

cs.DS2010

Multicut is FPT

Nicolas Bousquet, Jean Daligault, Stéphan Thomassé

Let $G = (V, E)$ be a graph on $n$ vertices and $R$ be a set of pairs of vertices in $V$ called \emph{requests}. A \emph{multicut} is a subset $F$ of $E$ such that every request $x y$ …

math.CO2010★ 4 cited

Edge Growth in Graph Cubes

Matt DeVos, Stéphan Thomassé

We show that for every connected graph $G$ of diameter $\geq 3$ , the graph $G^{3}$ has average degree $\geq 7/4 δ (G)$ . We also provide an example showing that this bound is best possib…