A Lower Bound on Probabilistic Algorithms for Distributive Ring Coloring

DOI10.1137/0404036zbMath0738.68007OpenAlexW1970330908MaRDI QIDQ3977297

Moni Naor

Publication date: 25 June 1992

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/1a65a6b05706fc20b59ec90253bafaddec837f5c

zbMATH Keywords

graph coloringprobabilistic algorithmdistributed computation

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)

Related Items (22)

Distributed computing with advice: information sensitivity of graph coloring ⋮ Exact Bounds for Distributed Graph Colouring ⋮ Local-Global Phenomena in Graphs ⋮ Distributed minimum dominating set approximations in restricted families of graphs ⋮ Large cuts with local algorithms on triangle-free graphs ⋮ Mallows permutations and finite dependence ⋮ Node and edge averaged complexities of local graph problems ⋮ Locally checkable problems in rooted trees ⋮ Distributed half-integral matching and beyond ⋮ Distributed $(\Delta+1)$-Coloring via Ultrafast Graph Shattering ⋮ Unnamed Item ⋮ Distributed half-integral matching and beyond ⋮ FINITELY DEPENDENT COLORING ⋮ An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model ⋮ Fooling views: a new lower bound technique for distributed computations under congestion ⋮ Leveraging Linial’s Locality Limit ⋮ A Time Hierarchy Theorem for the LOCAL Model ⋮ Randomized distributed decision ⋮ How long it takes for an ordinary node with an ordinary ID to output? ⋮ Finitely dependent processes are finitary ⋮ Distributed Lower Bounds for Ruling Sets ⋮ Linial for lists

This page was built for publication: A Lower Bound on Probabilistic Algorithms for Distributive Ring Coloring