Polylogarithmic-time deterministic network decomposition and distributed derandomization
From MaRDI portal
Publication:5144922
DOI10.1145/3357713.3384298OpenAlexW3034790637MaRDI QIDQ5144922
Václav Rozhoň, Mohsen Ghaffari
Publication date: 19 January 2021
Published in: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1907.10937
Related Items (38)
Distributed independent sets in interval and segment intersection graphs ⋮ Sublinear-time distributed algorithms for detecting small cliques and even cycles ⋮ A fast distributed algorithm for \((\Delta+1)\)-edge-coloring ⋮ Distributed strong diameter network decomposition ⋮ Distributed minimum vertex coloring and maximum independent set in chordal graphs ⋮ Network Decomposition and Distributed Derandomization (Invited Paper) ⋮ Distributed Testing of Distance-k Colorings ⋮ Node and edge averaged complexities of local graph problems ⋮ Local problems on grids from the perspective of distributed algorithms, finitary factors, and descriptive combinatorics ⋮ Locally checkable problems in rooted trees ⋮ On the Locality of Nash-Williams Forest Decomposition and Star-Forest Decomposition ⋮ Component stability in low-space massively parallel computation ⋮ Distributed $(\Delta+1)$-Coloring via Ultrafast Graph Shattering ⋮ Distributed graph problems through an automata-theoretic lens ⋮ Distributed coloring of hypergraphs ⋮ The Complexity of Distributed Approximation of Packing and Covering Integer Linear Programs ⋮ Efficient Distributed Decomposition and Routing Algorithms in Minor-Free Networks and Their Applications ⋮ 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 ⋮ A Near-Optimal Deterministic Distributed Synchronizer ⋮ Uniting General-Graph and Geometric-Based Radio Networks via Independence Number Parametrization ⋮ Optimal Message-Passing with Noisy Beeps ⋮ Mini-workshop: Descriptive combinatorics, LOCAL algorithms and random processes. Abstracts from the mini-workshop held February 13--19, 2022 ⋮ Improved distributed \(\Delta\)-coloring ⋮ Distributed distance-\(r\) covering problems on sparse high-girth graphs ⋮ Superfast coloring in CONGEST via efficient color sampling ⋮ Distributed coloring and the local structure of unit-disk graphs ⋮ Distributed distance-\(r\) covering problems on sparse high-girth graphs ⋮ Superfast coloring in CONGEST via efficient color sampling ⋮ Distributed Spanner Approximation ⋮ Loosely-stabilizing maximal independent set algorithms with unreliable communications ⋮ Simple, Deterministic, Constant-Round Coloring in Congested Clique and MPC ⋮ Distributed Lower Bounds for Ruling Sets ⋮ Linial for lists ⋮ Efficient and competitive broadcast in multi-channel radio networks ⋮ Distributed graph problems through an automata-theoretic Lens ⋮ Constant round distributed domination on graph classes with bounded expansion
This page was built for publication: Polylogarithmic-time deterministic network decomposition and distributed derandomization