Distributed graph coloring: Fundamentals and recent developments
L Barenboim, M Elkin - 2013 - books.google.com
Page 1 MORGAN & CLAYPOOL PUBLISHERS Distributed Graph Coloring Fundamentals and
Recent Developments Leonid Barenboim Michael Elkin HESIS SYNTHESIS LECTURES ON …
Recent Developments Leonid Barenboim Michael Elkin HESIS SYNTHESIS LECTURES ON …
The locality of distributed symmetry breaking
Symmetry-breaking problems are among the most well studied in the field of distributed
computing and yet the most fundamental questions about their complexity remain open. In …
computing and yet the most fundamental questions about their complexity remain open. In …
Distributed (δ+ 1)-coloring in linear (in δ) time
L Barenboim, M Elkin - Proceedings of the forty-first annual ACM …, 2009 - dl.acm.org
The distributed (Δ+ 1)-coloring problem is one of most fundamental and well-studied
problems in Distributed Algorithms. Starting with the work of Cole and Vishkin in 86, there …
problems in Distributed Algorithms. Starting with the work of Cole and Vishkin in 86, there …
Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition
L Barenboim, M Elkin - Proceedings of the twenty-seventh ACM …, 2008 - dl.acm.org
We study the distributed maximal independent set (henceforth, MIS) problem on sparse
graphs. Currently, there are known algorithms with a sublogarithmic running time for this …
graphs. Currently, there are known algorithms with a sublogarithmic running time for this …
Distributed (∆+ 1)-coloring in sublogarithmic rounds
The (∆+ 1)-coloring problem is a fundamental symmetry breaking problem in distributed
computing. We give a new randomized coloring algorithm for (∆+ 1)-coloring running in O …
computing. We give a new randomized coloring algorithm for (∆+ 1)-coloring running in O …
Deterministic distributed vertex coloring in polylogarithmic time
L Barenboim, M Elkin - Journal of the ACM (JACM), 2011 - dl.acm.org
Consider an n-vertex graph G=(V, E) of maximum degree Δ, and suppose that each vertex
v∈ V hosts a processor. The processors are allowed to communicate only with their …
v∈ V hosts a processor. The processors are allowed to communicate only with their …
A log-star distributed maximal independent set algorithm for growth-bounded graphs
J Schneider, R Wattenhofer - Proceedings of the twenty-seventh ACM …, 2008 - dl.acm.org
We present a novel distributed algorithm for the maximal independent set (MIS) problem. On
growth-bounded graphs (GBG) our deterministic algorithm finishes in O (log* n) time, n …
growth-bounded graphs (GBG) our deterministic algorithm finishes in O (log* n) time, n …
Distributed maximal independent set using small messages
M Ghaffari - Proceedings of the Thirtieth Annual ACM-SIAM …, 2019 - SIAM
Abstract Maximal Independent Set (MIS) is one of the central problems in distributed graph
algorithms. The celebrated works of Luby [STOC'85] and Alon, Babai, and Itai [JALG'86] …
algorithms. The celebrated works of Luby [STOC'85] and Alon, Babai, and Itai [JALG'86] …
A new technique for distributed symmetry breaking
J Schneider, R Wattenhofer - Proceedings of the 29th ACM SIGACT …, 2010 - dl.acm.org
We introduce Multi-Trials, a new technique for symmetry breaking for distributed algorithms
and apply it to various problems in general graphs. For instance, we present three …
and apply it to various problems in general graphs. For instance, we present three …
Distributed∆-coloring plays hide-and-seek
We prove several new tight or near-tight distributed lower bounds for classic symmetry
breaking problems in graphs. As a basic tool, we first provide a new insightful proof that any …
breaking problems in graphs. As a basic tool, we first provide a new insightful proof that any …