15 citations · 87 across the 33 of their papers we have counts for
5 papers · 1 filter
Maximum Matchings in Geometric Intersection Graphs
Édouard Bonnet, Sergio Cabello, Wolfgang Mulzer
Let be an intersection graph of geometric objects in the plane. We show that a maximum matching in can be found in time with high probability, wher…
When Maximum Stable Set can be solved in FPT time
Édouard Bonnet, Nicolas Bousquet, Stéphan Thomassé +1
Maximum Independent Set (MIS for short) is in general graphs the paradigmatic -hard problem. In stark contrast, polynomial-time algorithms are known when the inputs are restr…
Fine-Grained Complexity of k-OPT in Bounded-Degree Graphs for Solving TSP
Édouard Bonnet, Yoichi Iwata, Bart M. P. Jansen +1
Local search is a widely-employed strategy for finding good solutions to Traveling Salesman Problem. We analyze the problem of determining whether the weight of a given cycle can b…
Constraint Generation Algorithm for the Minimum Connectivity Inference Problem
Édouard Bonnet, Diana-Elena Fălămaş, Rémi Watrigant
Given a hypergraph , the Minimum Connectivity Inference problem asks for a graph on the same vertex set as with the minimum number of edges such that the subgraph induced by…
Metric Dimension Parameterized by Treewidth
Édouard Bonnet, Nidhi Purohit
A resolving set of a graph is a subset of its vertices such that no two vertices of have the same distance vector to . The Metric Dimension problem asks for a resolv…