Polylogarithmic-time deterministic network decomposition and distributed derandomization
From MaRDI portal
Publication:5144922
Recommendations
- Network Decomposition and Distributed Derandomization (Invited Paper)
- On the Complexity of Distributed Network Decomposition
- A fast network-decomposition algorithm and its applications to constant-time distributed computation
- A fast network-decomposition algorithm and its applications to constant-time distributed computation (extended abstract)
- Deterministic distributed vertex coloring in polylogarithmic time
- Deterministic distributed vertex coloring in polylogarithmic time
- Fast distributed network decompositions and covers
- Distributed Strong Diameter Network Decomposition
- scientific article; zbMATH DE number 7774256
- Distributed core decomposition in probabilistic graphs
Cited in
(79)- A fast network-decomposition algorithm and its applications to constant-time distributed computation
- Improved distributed \(\Delta\)-coloring
- Loosely-stabilizing maximal independent set algorithms with unreliable communications
- 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
- 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
- Distributed graph problems through an automata-theoretic lens
- Mini-workshop: Descriptive combinatorics, LOCAL algorithms and random processes. Abstracts from the mini-workshop held February 13--19, 2022
- Towards a polynomial-time randomized algorithm for closed product-form networks
- Distributed spanner approximation
- Network Decomposition and Distributed Derandomization (Invited Paper)
- Distributed Testing of Distance-k Colorings
- Distributed (+1)-coloring via ultrafast graph shattering
- On the Use of Randomness in Local Distributed Graph Algorithms
- Distributed Strong Diameter Network Decomposition
- Simple, Deterministic, Constant-Round Coloring in Congested Clique and MPC
- Distributed Lower Bounds for Ruling Sets
- 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
- Superfast coloring in CONGEST via efficient color sampling
- Distributed distance-\(r\) covering problems on sparse high-girth graphs
- Node and edge averaged complexities of local graph problems
- Local problems on grids from the perspective of distributed algorithms, finitary factors, and descriptive combinatorics
- Component stability in low-space massively parallel computation
- 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
- Polylogarithmic-Time Deterministic Network Decomposition and Distributed Derandomization
- Loosely-Stabilizing Maximal Independent Set Algorithms with Unreliable Communications
- The power of multi-step Vizing chains
- Faster deterministic distributed MIS and approximate matching
- Local conflict coloring revisited: Linial for lists
- Classification of distributed binary labeling problems
- The complexity landscape of distributed locally checkable problems on trees
- Improved distributed approximations for maximum independent set
- Coloring fast without learning your neighbors' colors
- Distributed domination on sparse graph classes
- Near-optimal distributed dominating set in bounded arboricity graphs
- Secured distributed algorithms without hardness assumptions
- Approximating bipartite minimum vertex cover in the Congest model
- Sample-and-gather: fast ruling set algorithms in the low-memory MPC model
- Exponential speedup over locality in \textsf{MPC} with optimal memory
- Faster leader election via mobile agents and its applications
- The message complexity of distributed graph optimization
- The distributed complexity of locally checkable labeling problems beyond paths and trees
- Local distributed rounding: generalized to MIS, matching, set cover, and beyond
- Distributed symmetry breaking on power graphs via sparsification
- Optimal message-passing with noisy beeps
- Borel versions of the local lemma and local algorithms for graphs of finite asymptotic separation index
- Fast algorithms for Vizing's theorem on bounded degree graphs
- Locally-iterative (+1)-coloring in sublinear (in ) rounds
- A near-optimal low-energy deterministic distributed SSSP with ramifications on congestion and APSP
- Universally optimal information dissemination and shortest paths in the HYBRID distributed model
- Brief announcement: Local advice and local decompression
- A tight lower bound for 3-coloring grids in the online-LOCAL model
- Large-scale geometry of Borel graphs of polynomial growth
- Distributed independent sets in interval and segment intersection graphs
- Parallel derandomization for coloring
- Narrowing the \textsf{LOCAL-CONGEST} gaps in sparse networks via expander decompositions
- Distributed MIS in O( n) awake complexity
- Parallel, distributed, and quantum exact single-source shortest paths with negative edge weights
- Distributed edge coloring in time polylogarithmic in \({\Delta }\)
- Shared randomness helps with local distributed problems
- Shared randomness in locally checkable problems: the role of computational assumptions
- Efficient distributed decomposition and routing algorithms in minor-free networks and their applications
- Fully scalable MPC algorithms for Euclidean k-center
- Distributed independent sets in interval and segment intersection graphs
This page was built for publication: Polylogarithmic-time deterministic network decomposition and distributed derandomization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5144922)
