2 papers
cs.DC2012
On the Locality of Some NP-Complete Problems
Leonid Barenboim
We consider the distributed message-passing {LOCAL} model. In this model a communication network is represented by a graph where vertices host processors, and communication is perf…
cs.DC2010
Deterministic Distributed Vertex Coloring in Polylogarithmic Time
Leonid Barenboim, Michael Elkin
Consider an n-vertex graph G = (V,E) of maximum degree Delta, and suppose that each vertex v \in V hosts a processor. The processors are allowed to communicate only with their neig…