Linear-size hopsets with small hopbound, and constant-hopbound hopsets in RNC (Q2084978): Difference between revisions

@@ Property / cites work @@
+A Hierarchy of Lower Bounds for Sublinear Additive Spanners
+Normal rank
@@ Property / cites work @@
+Parallel approximate undirected shortest paths via low hop emulators
+Normal rank
@@ Property / cites work @@
+Fully dynamic (2 + ε) approximate all-pairs shortest paths with fast query and close to linear update time
+Normal rank
@@ Property / cites work @@
+Fast Approximate Shortest Paths in the Congested Clique
+Normal rank
@@ Property / cites work @@
+Q4023518
@@ Property / cites work: Q4023518 / rank @@
+Normal rank
@@ Property / cites work @@
+Negative-Weight Shortest Paths and Unit Capacity Minimum Cost Flow in Õ (<i>m</i><sup>10/7</sup> log <i>W</i>) Time (Extended Abstract)
+Normal rank
@@ Property / cites work @@
+Using Selective Path-Doubling for Parallel Shortest-Path Computations
+Normal rank
@@ Property / cites work @@
+Polylog-time and near-linear work approximation scheme for undirected shortest paths
+Normal rank
@@ Property / cites work @@
+Exponentially Faster Shortest Paths in the Congested Clique
+Normal rank
@@ Property / cites work @@
+Computing almost shortest paths
@@ Property / cites work: Computing almost shortest paths / rank @@
+Normal rank
@@ Property / cites work @@
+Distributed exact shortest paths in sublinear time
+Normal rank
@@ Property / cites work @@
+On Efficient Distributed Construction of Near Optimal Routing Schemes
+Normal rank
@@ Property / cites work @@
+Near-Optimal Distributed Routing with Low Memory
@@ Property / cites work: Near-Optimal Distributed Routing with Low Memory / rank @@
+Normal rank
@@ Property / cites work @@
+Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths
+Normal rank
@@ Property / cites work @@
+$(1 + \epsilon,\beta)$-Spanner Constructions for General Graphs
+Normal rank
@@ Property / cites work @@
+Efficient algorithms for constructing \((1+\epsilon,\beta)\)-spanners in the distributed and streaming models
+Normal rank
@@ Property / cites work @@
+Parallel Metric Tree Embedding Based on an Algebraic View on Moore-Bellman-Ford
+Normal rank
@@ Property / cites work @@
+Q5092347
@@ Property / cites work: Q5092347 / rank @@
+Normal rank
@@ Property / cites work @@
+Deterministic sorting in O(nloglogn) time and linear space
+Normal rank
@@ Property / cites work @@
+Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time
+Normal rank
@@ Property / cites work @@
+A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
+Normal rank
@@ Property / cites work @@
+Thorup-Zwick emulators are universally optimal hopsets
+Normal rank
@@ Property / cites work @@
+A Randomized Parallel Algorithm for Single-Source Shortest Paths
+Normal rank
@@ Property / cites work @@
+Parallel computation and conflicts in memory access
+Normal rank
@@ Property / cites work @@
+Faster parallel algorithm for approximate shortest path
+Normal rank
@@ Property / cites work @@
+Packet routing and job-shop scheduling in \(O\) (congestion + dilation) steps
+Normal rank
@@ Property / cites work @@
+Fast Partial Distance Estimation and Applications
@@ Property / cites work: Fast Partial Distance Estimation and Applications / rank @@
+Normal rank
@@ Property / cites work @@
+Distributed distance computation and routing with small messages
+Normal rank
@@ Property / cites work @@
+Distributed approximation algorithms for weighted shortest paths
+Normal rank
@@ Property / cites work @@
+Max flows in O(nm) time, or better
@@ Property / cites work: Max flows in O(nm) time, or better / rank @@
+Normal rank
@@ Property / cites work @@
+Time–Work Tradeoffs of the Single-Source Shortest Paths Problem
+Normal rank
@@ Property / cites work @@
+Finding the maximum, merging, and sorting in a parallel computation model
+Normal rank
@@ Property / cites work @@
+Approximate distance oracles
@@ Property / cites work: Approximate distance oracles / rank @@
+Normal rank
@@ Property / cites work @@
+Spanners and emulators with sublinear distance errors
+Normal rank
@@ Property / cites work @@
+High-Probability Parallel Transitive-Closure Algorithms
+Normal rank