1 citations · 1 across the 6 of their papers we have counts for
12 papers
Almost tight distributed approximation for domination in sparse graph classes
Timothé Picavet
We study distributed approximation of Minimum Dominating Set in a very general class of sparse graphs, extending near-optimal approximation results from the minor-free setting to b…
Meta-Theorems for Cuttable Distributed Problems
Marthe Bonamy, Avinandan Das, Cyril Gavoille +3
We prove that given any -approximation LOCAL algorithm for Minimum Dominating Set (MDS) on planar graphs, we can construct an -round -approximation LOCAL algorithm…
The Distributed Complexity Landscape on Trees Depends on the Knowledge About the Network Size
Alkida Balliu, Sebastian Brandt, Fabian Kuhn +3
One of the central models in distributed computing is Linial's LOCAL model [SIAM J. Comp. 1992]. Over time, researchers have studied distributed graph problems in the LOCAL model u…
Testing H-freeness on sparse graphs, the case of bounded expansion
Samuel Humeau, Mamadou Moustapha Kanté, Daniel Mock +2
In property testing, a tester makes queries to (an oracle for) a graph and, on a graph having or being far from having a property P, it decides with high probability whether the gr…
Bipartite Turán number of paths and other trees
Marthe Bonamy, Théotime Leclere, Timothé Picavet
We solve a recent question of Caro, Patkós and Tuza by determining the exact maximum number of edges in a bipartite connected graph as a function of the longest path it contains as…
A polynomial bound on the pathwidth of graphs edge-coverable by shortest paths
Julien Baste, Lucas De Meyer, Ugo Giocanti +2
Dumas, Foucaud, Perez and Todinca (2024) recently proved that every graph whose edges can be covered by shortest paths has pathwidth at most . In this paper, we improve…
Distributed Approximation Algorithms for Minimum Dominating Set in Locally Nice Graphs
Marthe Bonamy, Cyril Gavoille, Timothé Picavet +1
We give a new, short proof that graphs embeddable in a given Euler genus- surface admit a simple -round -approximation distributed algorithm for Minimum Dominating Set…
Local Constant Approximation for Dominating Set on Graphs Excluding Large Minors
Marthe Bonamy, Cyril Gavoille, Timothé Picavet +1
We show that graphs excluding as a minor admit a -round -approximation deterministic distributed algorithm for Minimum Dominating Set. The result extends to Min…
Induced Disjoint Paths Without an Induced Minor
Pierre Aboulker, Édouard Bonnet, Timothé Picavet +1
We exhibit a new obstacle to the nascent algorithmic theory for classes excluding an induced minor. We indeed show that on the class of string graphs -- which avoids the 1-subdivis…
Distributed Binary Labeling Problems in High-Degree Graphs
Henrik Lievonen, Timothé Picavet, Jukka Suomela
Balliu et al. (DISC 2020) classified the hardness of solving binary labeling problems with distributed graph algorithms; in these problems the task is to select a subset of edges i…
A parameterized approximation scheme for the 2D-Knapsack problem with wide items
Michal Pilipczuk, Mathieu Mari, Timothe Picavet
We study a natural geometric variant of the classic Knapsack problem called 2D-Knapsack: we are given a set of axis-parallel rectangles and a rectangular bounding box, and the goal…
Distributed derandomization revisited
Sameep Dahal, Francesco d'Amore, Henrik Lievonen +2
One of the cornerstones of the distributed complexity theory is the derandomization result by Chang, Kopelowitz, and Pettie [FOCS 2016]: any randomized LOCAL algorithm that solves…