A Lower Bound on Probabilistic Algorithms for Distributive Ring Coloring
From MaRDI portal
Publication:3977297
DOI10.1137/0404036zbMath0738.68007MaRDI QIDQ3977297
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
68M10: Network design and communication in computer systems
68R05: Combinatorics in computer science
68R10: Graph theory (including graph drawing) in computer science
68W10: Parallel algorithms in computer science
Related Items
Local-Global Phenomena in Graphs, An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model, A Time Hierarchy Theorem for the LOCAL Model, Unnamed Item, Distributed $(\Delta+1)$-Coloring via Ultrafast Graph Shattering, How long it takes for an ordinary node with an ordinary ID to output?, Distributed Lower Bounds for Ruling Sets, Locally checkable problems in rooted trees, Distributed minimum dominating set approximations in restricted families of graphs, Finitely dependent processes are finitary, Linial for lists, Mallows permutations and finite dependence, Fooling views: a new lower bound technique for distributed computations under congestion, Randomized distributed decision, Distributed computing with advice: information sensitivity of graph coloring, Large cuts with local algorithms on triangle-free graphs, FINITELY DEPENDENT COLORING, Exact Bounds for Distributed Graph Colouring, Leveraging Linial’s Locality Limit
