Decentralized Low-Stretch Trees via Low Diameter Graph Decompositions
From MaRDI portal
Publication:6154194
DOI10.1137/22m1489034OpenAlexW4392820947MaRDI QIDQ6154194
Mohsen Ghaffari, Christoph Lenzen, Yuval Emek, Ruben Becker
Publication date: 19 March 2024
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/22m1489034
graph decompositionsdistributed graph algorithmsparallel graph algorithms(semi-)streaming graph algorithmsmetric tree embeddingslow-stretch trees
Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Randomized algorithms (68W20) Distributed algorithms (68W15) Online algorithms; streaming algorithms (68W27) Metric embeddings as related to computational problems and algorithms (68R12)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Nearly-linear work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs
- Streaming algorithm for graph spanners-single pass and constant processing time per edge
- Low diameter graph decompositions
- Efficient algorithms for constructing \((1+\epsilon,\beta)\)-spanners in the distributed and streaming models
- Distributed distance computation and routing with small messages
- On graph problems in a semi-streaming model
- Spectral sparsification via random spanners
- Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners
- Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
- Lower-Stretch Spanning Trees
- Complexity of network synchronization
- Graph spanners
- Fast Distributed Construction of Smallk-Dominating Sets and Applications
- A Graph-Theoretic Game and Its Application to the k-Server Problem
- A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees
- Polylog-time and near-linear work approximation scheme for undirected shortest paths
- Distributed Computing: A Locality-Sensitive Approach
- Near-Optimal Distributed Maximum Flow
- A Hierarchy of Lower Bounds for Sublinear Additive Spanners
- Distributed Algorithms for Planar Networks II: Low-Congestion Shortcuts, MST, and Min-Cut
- Parallel Metric Tree Embedding Based on an Algebraic View on Moore-Bellman-Ford
- Distributed Verification and Hardness of Distributed Approximation
- On the complexity of local distributed graph problems
- Oblivious Routing for the Lp-norm
- Dynamic low-stretch trees via dynamic low-diameter decompositions
- Solving SDD linear systems in nearly m log 1/2 n time
- Distributed Strong Diameter Network Decomposition
- Using petal-decompositions to build a low stretch spanning tree
- Approaching Optimality for Solving SDD Linear Systems
- Algorithms – ESA 2004
- A Nearly-m log n Time Solver for SDD Linear Systems
- Single-Source Shortest Paths in the CONGEST Model with Improved Bound
- A tight bound on approximating arbitrary metrics by tree metrics
- Efficient distributed approximation algorithms via probabilistic tree embeddings
