Stéphan Thomassé

activity

20222026

most citedBounded twin-width graphs are polynomially

χ

-bounded

2 citations · 5 across the 7 of their papers we have counts for

collaborators

Showing cs.DSShow all

2 papers · 1 filter

cs.DS2026

A combinatorial framework for clustering graph states: Algorithms and hardness for rank-integrity

Romain Bourneuf, Nathan Claudet, Sang Yoon Kim +3

We introduce a new notion of distance between two graph states $∣ G ⟩$ and $∣ G^{'} ⟩$ on the same set of qubits. This distance is the minimum number of ancilla qubits in a gr…

cs.DS2022

A quasi-quadratic vertex Kernel for Cograph edge editing

Christophe Crespelle, Rémi Pellerin, Stéphan Thomassé

We provide a $O (k^{2} log k)$ vertex kernel for cograph edge editing. This improves a cubic kernel found by Guillemot, Havet, Paul and Perez [1] which involved four reductio…