24 citations · 104 across the 24 of their papers we have counts for
5 papers · 1 filter
EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs
Marthe Bonamy, Édouard Bonnet, Nicolas Bousquet +6
A (unit) disk graph is the intersection graph of closed (unit) disks in the plane. Almost three decades ago, an elegant polynomial-time algorithm was found for \textsc{Maximum Cliq…
Parameterized Complexity of Independent Set in H-Free Graphs
Édouard Bonnet, Nicolas Bousquet, Pierre Charbit +2
In this paper, we investigate the complexity of Maximum Independent Set (MIS) in the class of -free graphs, that is, graphs excluding a fixed graph as an induced subgraph. Given…
A New Graph Parameter To Measure Linearity
Pierre Charbit, Michel Habib, Lalla Mouatadid +1
Consider a sequence of LexBFS vertex orderings σ1, σ2, . . . where each ordering σi is used to break ties for σi+1. Since the total number of vertex orderings of a finite graph is…
Detecting 2-joins faster
Pierre Charbit, Michel Habib, Nicolas Trotignon +1
2-joins are edge cutsets that naturally appear in the decomposition of several classes of graphs closed under taking induced subgraphs, such as balanced bipartite graphs, even-hole…
A Note On Computing Set Overlap Classes
Pierre Charbit, Michel Habib, Vincent Limouzy +3
Let be a finite set of elements and a family of subsets of Two sets and of overlap if $X_i \…