15 citations · 87 across the 33 of their papers we have counts for
5 papers · 1 filter
On the Complexity of Various Parameterizations of Common Induced Subgraph Isomorphism
Faisal N. Abu-Khzam, Édouard Bonnet, Florian Sikora
In the Maximum Common Induced Subgraph problem (henceforth MCIS), given two graphs and , one looks for a graph with the maximum number of vertices being both an induced…
A 0.821-ratio purely combinatorial algorithm for maximum -vertex cover in bipartite graphs
Edouard Bonnet, Bruno Escoffier, Vangelis Paschos +1
Our goal in this paper is to propose a \textit{combinatorial algorithm} that beats the only such algorithm known previously, the greedy one. We study the polynomial approximation o…
Complexity of Grundy coloring and its variants
Edouard Bonnet, Florent Foucaud, Eun Jung Kim +1
The Grundy number of a graph is the maximum number of colors used by the greedy coloring algorithm over all vertex orderings. In this paper, we study the computational complexity o…
Havannah and TwixT are PSPACE-complete
Edouard Bonnet, Florian Jamain, Abdallah Saffidine
Numerous popular abstract strategy games ranging from Hex and Havannah to Lines of Action belong to the class of connection games. Still, very few complexity results on such games…
Sparsification and subexponential approximation
Edouard Bonnet, Vangelis Th. Paschos
Instance sparsification is well-known in the world of exact computation since it is very closely linked to the Exponential Time Hypothesis. In this paper, we extend the concept of…