Abstract The Maximal Independent Set (MIS) problem is one of the basics in the study of
locality in distributed graph algorithms. This paper presents a very simple randomized …

Computational and biological systems are often distributed so that processors (cells) jointly
solve a task, without any of them receiving all inputs or observing all outputs. Maximal …

We consider the problem of computing a maximal independent set (MIS) in an extremely
harsh broadcast model that relies only on carrier sensing. The model consists of an …

We provide a tight analysis that settles the round complexity of the well-studied parallel
randomized greedy MIS algorithm, thus answering the main open question of Blelloch …

This paper studies the problem of having mobile robots in a multi-robot system maintain an
estimate of the relative position and relative orientation of near-by robots in the environment …

We show how to construct an overlay network of constant degree and diameter O (log n) in
time O (log n) starting from an arbitrary weakly connected graph. We assume a synchronous …

Since in general it is NP-hard to solve the minimum dominating set problem even
approximatively, a lot of work has been dedicated to central and distributed approximation …

A dominating set is a subset of the nodes of a graph such that all nodes are in the set or
adjacent to a node in the set. A minimum dominating set approximation is a dominating set …

Group therapy is one of the major clinical interventions to help patients with mental
disorders. However, finding an effective therapy group is very challenging, since there are …

Fault tolerance is one of the main concepts in distributed computing. It has been tackled from
different angles, eg by building replicated systems that can survive crash failures of …