Zobrazeno 1 - 10
of 50
pro vyhledávání: '"Rabie, Mikaël"'
We study the awake complexity of graph problems that belong to the class O-LOCAL, which includes a large subset of problems solvable by sequential greedy algorithms, such as $(\Delta+1)$-coloring, maximal independent set, maximal matching, etc. It is
Externí odkaz:
http://arxiv.org/abs/2410.20499
Autor:
Balliu, Alkida, Fraigniaud, Pierre, Lambein-Monette, Patrick, Olivetti, Dennis, Rabie, Mikael
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 2022]. We focus on the vertex coloring problem, and our contributions c
Externí odkaz:
http://arxiv.org/abs/2408.10971
This paper formalises the Canadian Traveller problem as a positional two-player game on graphs. We consider two variants depending on whether an edge is blocked. In the locally-informed variant, the traveller learns if an edge is blocked upon reachin
Externí odkaz:
http://arxiv.org/abs/2407.16491
Autor:
Balliu, Alkida, Ghaffari, Mohsen, Kuhn, Fabian, Modanese, Augusto, Olivetti, Dennis, Rabie, Mikaël, Suomela, Jukka, Uitto, Jara
By prior work, we have many results related to distributed graph algorithms for problems that can be defined with local constraints; the formal framework used in prior work is locally checkable labeling problems (LCLs), introduced by Naor and Stockme
Externí odkaz:
http://arxiv.org/abs/2407.05445
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 which round they are awake, and on which round they are sleeping. Two (
Externí odkaz:
http://arxiv.org/abs/2405.10058
Consider a dynamic network and a given distributed problem. At any point in time, there might exist several solutions that are equally good with respect to the problem specification, but that are different from an algorithmic perspective, because som
Externí odkaz:
http://arxiv.org/abs/2304.05831
In this paper, we study temporal graphs arising from mobility models, where vertices correspond to agents moving in space and edges appear each time two agents meet. We propose a rather natural one-dimensional model. If each pair of agents meets exac
Externí odkaz:
http://arxiv.org/abs/2302.07666
We propose a way to transform synchronous distributed algorithms solving locally greedy and mendable problems into self-stabilizing algorithms in anonymous networks. Mendable problems are a generalization of greedy problems where any partial solution
Externí odkaz:
http://arxiv.org/abs/2208.14700
We present a wait-free algorithm for proper coloring the n nodes of the asynchronous cycle $C_n$, where each crash-prone node starts with its (unique) identifier as input. The algorithm is independent of $n \geq 3$, and runs in $\mathrm{O}(\log^* n)$
Externí odkaz:
http://arxiv.org/abs/2207.11198
Recoloring a graph is about finding a sequence of proper colorings of this graph from an initial coloring $\sigma$ to a target coloring $\eta$. Adding the constraint that each pair of consecutive colorings must differ on exactly one vertex, one asks:
Externí odkaz:
http://arxiv.org/abs/2203.08885