Decentralized Low-Stretch Trees via Low Diameter Graph Decompositions

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

zbMATH Keywords

graph decompositionsdistributed graph algorithmsparallel graph algorithms(semi-)streaming graph algorithmsmetric tree embeddingslow-stretch trees

Mathematics Subject Classification ID

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
• Near-optimal approximate shortest paths and transshipment in distributed and streaming models

This page was built for publication: Decentralized Low-Stretch Trees via Low Diameter Graph Decompositions