33 citations · 94 across the 15 of their papers we have counts for
4 papers · 1 filter
Clique-Stable Set separation in perfect graphs with no balanced skew-partitions
Aurélie Lagoutte, Théophile Trunck
Inspired by a question of Yannakakis on the Vertex Packing polytope of perfect graphs, we study the Clique-Stable Set Separation in a non-hereditary subclass of perfect graphs. A c…
The complexity of Shortest Common Supersequence for inputs with no identical consecutive letters
Aurélie Lagoutte, Sébastien Tavenas
The Shortest Common Supersequence problem (SCS for short) consists in finding a shortest common supersequence of a finite set of words on a fixed alphabet Sigma. It is well-known t…
The Erdős-Hajnal Conjecture for Paths and Antipaths
Nicolas Bousquet, Aurélie Lagoutte, Stéphan Thomassé
We prove that for every k, there exists such that every graph G on n vertices not inducing a path and its complement contains a clique or a stable set of size $n^{c_k…
Clique versus Independent Set
Nicolas Bousquet, Aurélie Lagoutte, Stéphan Thomassé
Yannakakis' Clique versus Independent Set problem (CL-IS) in communication complexity asks for the minimum number of cuts separating cliques from stable sets in a graph, called CS-…