5 papers · 1 filter
A Simple Construction of Locally Checkable Problems Filling the LOCAL Complexity Gaps in Graphs with Arbitrary Large Degrees
Filippo Casagrande, Pierre Fraigniaud, Benjamin Jauregui +1
We show that the complexity gaps in the round complexities of locally checkable labeling (LCL) problems are not due to the fact that solutions to LCL problems must be locally check…
Deterministic Even-Cycle Detection in Broadcast CONGEST
Pierre Fraigniaud, Maël Luce, Frédéric Magniez +1
We show that, for every , -freeness can be decided in rounds in the Broadcast CONGEST model, by a deterministic algorithm. This (deterministic) roun…
Solving Sequential Greedy Problems Distributedly with Sub-Logarithmic Energy Cost
Alkida Balliu, Pierre Fraigniaud, Dennis Olivetti +1
We study the awake complexity of graph problems that belong to the class O-LOCAL, which includes a subset of problems solvable by sequential greedy algorithms, such as -colo…
Asynchronous Fault-Tolerant Distributed Proper Coloring of Graphs
Alkida Balliu, Pierre Fraigniaud, Patrick Lambein-Monette +2
We revisit asynchronous computing in networks of crash-prone processes, under the asynchronous variant of the standard LOCAL model, recently introduced by Fraigniaud et al. [DISC 2…
Distributed Coloring in the SLEEPING Model
Fabien Dufoulon, Pierre Fraigniaud, Mikaël Rabie +1
In distributed network computing, a variant of the LOCAL model has been recently introduced, referred to as the SLEEPING model. In this model, nodes have the ability to decide on w…