5 citations · 23 across the 20 of their papers we have counts for
13 papers · 1 filter
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…
Even-Cycle Detection in the Randomized and Quantum CONGEST Model
Pierre Fraigniaud, Mael Luce, Frederic Magniez +1
We show that, for every , -freeness can be decided in rounds in the \CONGEST{} model by a randomized Monte-Carlo distributed algorithm with one-side…
Distributed Certification for Classes of Dense Graphs
Pierre Fraigniaud, Frédéric Mazoit, Pedro Montealegre +2
A proof-labeling scheme (PLS) for a boolean predicate on labeled graphs is a mechanism used for certifying the legality with respect to of global network states in a distri…
On the Power of Threshold-Based Algorithms for Detecting Cycles in the CONGEST Model
Pierre Fraigniaud, Maël Luce, Ioan Todinca
It is known that, for every , -freeness can be decided by a generic Monte-Carlo algorithm running in rounds in the CONGEST model. For $2\leq k\leq…
Energy-Efficient Distributed Algorithms for Synchronous Networks
Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport +1
We study the design of energy-efficient algorithms for the LOCAL and CONGEST models. Specifically, as a measure of complexity, we consider the maximum, taken over all the edges, or…
Computing Power of Hybrid Models in Synchronous Networks
Pierre Fraigniaud, Pedro Montealegre, Pablo Paredes +3
During the last two decades, a small set of distributed computing models for networks have emerged, among which LOCAL, CONGEST, and Broadcast Congested Clique (BCC) play a prominen…