Distributed Symmetry Breaking on Power Graphs via Sparsification

DOI10.1145/3583668.3594579arXiv2302.06878OpenAlexW4380880097MaRDI QIDQ6202239

Jara Uitto, Yannic Maus, Unnamed Author

Publication date: 26 March 2024

Published in: Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2302.06878

zbMATH Keywords

shatteringdistributed algorithmsparsificationmaximal independent setpower graphsruling setsCONGEST model

Mathematics Subject Classification ID

Distributed systems (68M14) Distributed algorithms (68W15)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Symmetry breaking depending on the chromatic number or the neighborhood growth
• Deterministic distributed ruling sets of line graphs
• Improved distributed \(\Delta\)-coloring
• Correlation clustering in data streams
• Toward more localized local algorithms: removing assumptions concerning global knowledge
• Toward Optimal Bounds in the Congested Clique
• Super-Fast 3-Ruling Sets.
• The Locality of Distributed Symmetry Breaking
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• Locality in Distributed Graph Algorithms
• Distributed Computing: A Locality-Sensitive Approach
• An Improved Distributed Algorithm for Maximal Independent Set
• Chernoff–Hoeffding Bounds for Applications with Limited Independence
• On the complexity of local distributed graph problems
• A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths
• Distributed Testing of Distance-k Colorings
• Distributed $(\Delta+1)$-Coloring via Ultrafast Graph Shattering
• Polylogarithmic-time deterministic network decomposition and distributed derandomization
• Deterministic Distributed Dominating Set Approximation in the CONGEST Model
• An Automatic Speedup Theorem for Distributed Problems
• The Complexity of (Δ+1) Coloring in Congested Clique, Massively Parallel Computation, and Centralized Local Computation
• Near-Additive Spanners In Low Polynomial Deterministic CONGEST Time
• Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover
• Sublinear Algorithms for (Δ + 1) Vertex Coloring
• Distributed Maximal Independent Set using Small Messages
• Sparsifying Distributed Algorithms with Ramifications in Massively Parallel Computation and Centralized Local Computation
• Distributed MIS via All-to-All Communication
• A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs
• Distributed Approximation on Power Graphs
• Distance-2 Coloring in the CONGEST Model
• Efficient Deterministic Distributed Coloring with Small Bandwidth
• Distributed Lower Bounds for Ruling Sets
• Superfast coloring in CONGEST via efficient color sampling
• Distributed algorithms for the Lovász local lemma and graph coloring
• Models and approximation algorithms for channel assignment in radio networks
• A deterministic algorithm for the MST problem in constant rounds of congested clique

This page was built for publication: Distributed Symmetry Breaking on Power Graphs via Sparsification