1992/02/01 by Nathan Linial · 894 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Binary logarithm #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Discrete mathematics #Distributed algorithm #Distributed computing #Graph #Locality #Mathematics #Omega #Optimization and Search Problems #Time complexity #Upper and lower bounds #Vertex (graph theory)
paper · doi:10.1137/0221015
published in SIAM Journal on Computing 21(1), 193-201 (Society for Industrial and Applied Mathematics)
openalex publication_date 1992/02/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/14
This paper concerns a number of algorithmic problems on graphs and how they may be solved in a distributed fashion. The computational model is such that each node of the graph is occupied by a processor which has its own ID. Processors are restricted to collecting data from others which are at a distance at most t away from them in t time units, but are otherwise computationally unbounded. This model focuses on the issue of locality in distributed processing, namely, to what extent a global solution to a computational problem can be obtained from locally available data. Three results are proved within this model: • A 3-coloring of an n-cycle requires time Ω (log ^ * n). This bound is tight, by previous work of Cole and Vishkin. • Any algorithm for coloring the d-regular tree of radius r which runs for time at most 2r/3 requires at least Ω (√ d ) colors. • In an n-vertex graph of largest degree Δ , an O(Δ 2 )-coloring may be found in time O(log ^ * n).