The Locality of Distributed Symmetry Breaking
From MaRDI portal
Publication:3177792
DOI10.1145/2903137zbMath1426.68020arXiv1202.1983OpenAlexW2467514673MaRDI QIDQ3177792
No author found.
Publication date: 2 August 2018
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1202.1983
Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15) Distributed systems (68M14)
Related Items (47)
Nearly Optimal Local Broadcasting in the SINR Model with Feedback ⋮ A Fast Network-Decomposition Algorithm and Its Applications to Constant-Time Distributed Computation ⋮ Can we locally compute sparse connected subgraphs? ⋮ Deterministic Subgraph Detection in Broadcast CONGEST. ⋮ Distributed minimum vertex coloring and maximum independent set in chordal graphs ⋮ Network Decomposition and Distributed Derandomization (Invited Paper) ⋮ What can be sampled locally? ⋮ Improved deterministic distributed matching via rounding ⋮ Derandomizing local distributed algorithms under bandwidth restrictions ⋮ Node and edge averaged complexities of local graph problems ⋮ Linear-in-\(\varDelta \) lower bounds in the LOCAL model ⋮ Time-optimal construction of overlay networks ⋮ Distributed half-integral matching and beyond ⋮ Exact distributed sampling ⋮ Distributed $(\Delta+1)$-Coloring via Ultrafast Graph Shattering ⋮ Distributed half-integral matching and beyond ⋮ Distributed graph problems through an automata-theoretic lens ⋮ Distributed coloring of hypergraphs ⋮ Distributed MIS in O(log log n) Awake Complexity ⋮ Distributed MIS with Low Energy and Time Complexities ⋮ Distributed Symmetry Breaking on Power Graphs via Sparsification ⋮ Optimal Message-Passing with Noisy Beeps ⋮ Distributed Self-Stabilizing MIS with Few States and Weak Communication ⋮ Distributed Local Approximation Algorithms for Maximum Matching in Graphs and Hypergraphs ⋮ Breaking the linear-memory barrier in \(\mathsf{MPC}\): fast \(\mathsf{MIS}\) on trees with strongly sublinear memory ⋮ An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model ⋮ Distributed Graph Algorithms and their Complexity: An Introduction ⋮ Local Algorithms for Bounded Degree Sparsifiers in Sparse Graphs ⋮ (Delta+1) Coloring in the Congested Clique Model ⋮ Improved distributed \(\Delta\)-coloring ⋮ Distributed backup placement in networks ⋮ A Time Hierarchy Theorem for the LOCAL Model ⋮ Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring ⋮ Local computation algorithms for graphs of non-constant degrees ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Improved distributed algorithms for coloring interval graphs with application to multicoloring trees ⋮ Dynamic networks of finite state machines ⋮ Superfast coloring in CONGEST via efficient color sampling ⋮ Distributed coloring and the local structure of unit-disk graphs ⋮ Superfast coloring in CONGEST via efficient color sampling ⋮ Distributed algorithms for the Lovász local lemma and graph coloring ⋮ Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs ⋮ Loosely-stabilizing maximal independent set algorithms with unreliable communications ⋮ Distributed Lower Bounds for Ruling Sets ⋮ Linial for lists ⋮ Distributed graph problems through an automata-theoretic Lens
This page was built for publication: The Locality of Distributed Symmetry Breaking
