15 citations · 87 across the 33 of their papers we have counts for
3 papers · 2 filters
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…