Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models
From MaRDI portal
Publication:4989920
DOI10.1137/19M1286955zbMath1491.68264arXiv1607.05127MaRDI QIDQ4989920
Andreas Karrenbauer, Sebastian Forster, Christoph Lenzen, Ruben Becker
Publication date: 27 May 2021
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1607.05127
Programming involving graphs or networks (90C35) Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Distributed algorithms (68W15) Online algorithms; streaming algorithms (68W27)
Related Items (9)
Single-source shortest paths in the CONGEST model with improved bounds ⋮ Minimum cost flow in the CONGEST model ⋮ Online Spanners in Metric Spaces ⋮ Brief Announcement: Minimum Cost Maximum Flow in the CONGEST Model ⋮ Brief Announcement: The Laplacian Paradigm in Deterministic Congested Clique ⋮ Fast approximate shortest paths in the congested clique ⋮ A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths ⋮ Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time ⋮ Approximate minimum directed spanning trees under congestion
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Superlinear lower bounds for multipass graph processing
- Streaming algorithm for graph spanners-single pass and constant processing time per edge
- A parallel priority queue with constant time operations
- Thorup-Zwick emulators are universally optimal hopsets
- Further algebraic algorithms in the congested clique model and applications to graph-theoretic problems
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Algebraic methods in the congested clique
- Efficient algorithms for constructing \((1+\epsilon,\beta)\)-spanners in the distributed and streaming models
- On graph problems in a semi-streaming model
- Using Selective Path-Doubling for Parallel Shortest-Path Computations
- Undirected single-source shortest paths with positive integer weights in linear time
- Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners
- On a routing problem
- An Unconditional Lower Bound on the Time-Approximation Trade-off for the Distributed Minimum Spanning Tree Problem
- Lower-Stretch Spanning Trees
- Graph Distances in the Data-Stream Model
- Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
- Time–Work Tradeoffs of the Single-Source Shortest Paths Problem
- A Randomized Parallel Algorithm for Single-Source Shortest Paths
- Time-work tradeoffs for parallel algorithms
- Polylog-time and near-linear work approximation scheme for undirected shortest paths
- Distributed Computing: A Locality-Sensitive Approach
- Hollow Heaps
- A Hierarchy of Lower Bounds for Sublinear Additive Spanners
- Negative-Weight Shortest Paths and Unit Capacity Minimum Cost Flow in Õ (m10/7 log W) Time (Extended Abstract)
- Generalized Preconditioning and Undirected Minimum-Cost Flow
- Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time
- Δ-stepping: a parallelizable shortest path algorithm
- Scaling Algorithms for the Shortest Paths Problem
- Distributed Verification and Hardness of Distributed Approximation
- Distributed exact shortest paths in sublinear time
- Fast Approximate Shortest Paths in the Congested Clique
- Fully dynamic (2 + ε) approximate all-pairs shortest paths with fast query and close to linear update time
- Fibonacci heaps and their uses in improved network optimization algorithms
- Improved distributed algorithms for exact shortest paths
- Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths
- Distributed approximation algorithms for weighted shortest paths
- A Faster Strongly Polynomial Minimum Cost Flow Algorithm
- A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs
- A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
- An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations
- Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs
- Fast routing table construction using small messages
- Minimum-Weight Spanning Tree Construction in O(log log n) Communication Rounds
- Automata, Languages and Programming
- Combinatorial optimization. Theory and algorithms
This page was built for publication: Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models
