Linear-size hopsets with small hopbound, and constant-hopbound hopsets in RNC
From MaRDI portal
Publication:2084978
DOI10.1007/s00446-022-00431-zOpenAlexW4283698215MaRDI QIDQ2084978
Publication date: 14 October 2022
Published in: Distributed Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00446-022-00431-z
Cites Work
- Unnamed Item
- Unnamed Item
- Parallel computation and conflicts in memory access
- Packet routing and job-shop scheduling in \(O\) (congestion + dilation) steps
- Thorup-Zwick emulators are universally optimal hopsets
- Efficient algorithms for constructing \((1+\epsilon,\beta)\)-spanners in the distributed and streaming models
- Distributed distance computation and routing with small messages
- Fast Partial Distance Estimation and Applications
- Using Selective Path-Doubling for Parallel Shortest-Path Computations
- High-Probability Parallel Transitive-Closure Algorithms
- Spanners and emulators with sublinear distance errors
- Finding the maximum, merging, and sorting in a parallel computation model
- Time–Work Tradeoffs of the Single-Source Shortest Paths Problem
- A Randomized Parallel Algorithm for Single-Source Shortest Paths
- Polylog-time and near-linear work approximation scheme for undirected shortest paths
- 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)
- Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time
- Parallel Metric Tree Embedding Based on an Algebraic View on Moore-Bellman-Ford
- $(1 + \epsilon,\beta)$-Spanner Constructions for General Graphs
- Deterministic sorting in O(nloglogn) time and linear space
- Distributed exact shortest paths in sublinear time
- Faster parallel algorithm for approximate shortest path
- Parallel approximate undirected shortest paths via low hop emulators
- 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
- Approximate distance oracles
- Near-Optimal Distributed Routing with Low Memory
- Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths
- Distributed approximation algorithms for weighted shortest paths
- A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
- On Efficient Distributed Construction of Near Optimal Routing Schemes
- Max flows in O(nm) time, or better
- Exponentially Faster Shortest Paths in the Congested Clique
- Computing almost shortest paths
This page was built for publication: Linear-size hopsets with small hopbound, and constant-hopbound hopsets in RNC
