Showing cs.DCShow all
3 papers · 1 filter
cs.DC2021
Sleeping Model: Local and Dynamic Algorithms
Tzalik Maimon
In recent years the sleeping model came to the focus of researchers. In this model nodes can go into a sleep state in which they spend no energy but at the same time cannot receive…
cs.DC2021
Deterministic Logarithmic Completeness in the Distributed Sleeping Model
Leonid Barenboim, Tzalik Maimon
We provide a deterministic scheme for solving any decidable problem in the distributed {sleeping model}. The sleeping model is a generalization of the standard message-passing mode…
cs.DC2016
Deterministic Distributed (Delta + o(Δ))-Edge-Coloring, and Vertex-Coloring of Graphs with Bounded Diversity
Leonid Barenboim, Michael Elkin, Tzalik Maimon
We consider coloring problems in the distributed message-passing setting. The previously-known deterministic algorithms for edge-coloring employed at least (2Delta - 1) colors, eve…