Lower Bounds on Sparse Spanners, Emulators, and Diameter-Reducing Shortcuts (Q5157382): Difference between revisions

@@ Property / cites work @@
+The 4/3 Additive Spanner Exponent Is Tight
@@ Property / cites work: The 4/3 Additive Spanner Exponent Is Tight / rank @@
+Normal rank
@@ Property / cites work @@
+A Hierarchy of Lower Bounds for Sublinear Additive Spanners
+Normal rank
@@ Property / cites work @@
+Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
+Normal rank
@@ Property / cites work @@
+Testing subgraphs in large graphs
@@ Property / cites work: Testing subgraphs in large graphs / rank @@
+Normal rank
@@ Property / cites work @@
+The convex hull of the integer points in a large ball
+Normal rank
@@ Property / cites work @@
+Additive spanners and (α, β)-spanners
@@ Property / cites work: Additive spanners and (α, β)-spanners / rank @@
+Normal rank
@@ Property / cites work @@
+On Sets of Integers Which Contain No Three Terms in Arithmetical Progression
+Normal rank
@@ Property / cites work @@
+Linear Size Distance Preservers
@@ Property / cites work: Linear Size Distance Preservers / rank @@
+Normal rank
@@ Property / cites work @@
+Very Sparse Additive Spanners and Emulators
@@ Property / cites work: Very Sparse Additive Spanners and Emulators / rank @@
+Normal rank
@@ Property / cites work @@
+Better Distance Preservers and Additive Spanners
@@ Property / cites work: Better Distance Preservers and Additive Spanners / rank @@
+Normal rank
@@ Property / cites work @@
+Efficient construction of directed hopsets and parallel approximate shortest paths
+Normal rank
@@ Property / cites work @@
+New Additive Spanners
@@ Property / cites work: New Additive Spanners / rank @@
+Normal rank
@@ Property / cites work @@
+Sparse Sourcewise and Pairwise Distance Preservers
+Normal rank
@@ Property / cites work @@
+All-Pairs Almost Shortest Paths
@@ Property / cites work: All-Pairs Almost Shortest Paths / rank @@
+Normal rank
@@ Property / cites work @@
+Q5011874
@@ Property / cites work: Q5011874 / rank @@
+Normal rank
@@ Property / cites work @@
+$(1 + \epsilon,\beta)$-Spanner Constructions for General Graphs
+Normal rank
@@ Property / cites work @@
+Nearly work-efficient parallel algorithm for digraph reachability
+Normal rank
@@ Property / cites work @@
+Q4471356
@@ Property / cites work: Q4471356 / rank @@
+Normal rank
@@ Property / cites work @@
+Thorup-Zwick emulators are universally optimal hopsets
+Normal rank
@@ Property / cites work @@
+Additive Spanners: A Simple Construction
@@ Property / cites work: Additive Spanners: A Simple Construction / rank @@
+Normal rank
@@ Property / cites work @@
+Low distortion spanners
@@ Property / cites work: Low distortion spanners / rank @@
+Normal rank
@@ Property / cites work @@
+Q4281646
@@ Property / cites work: Q4281646 / rank @@
+Normal rank
@@ Property / cites work @@
+Shortcutting Planar Digraphs
@@ Property / cites work: Shortcutting Planar Digraphs / rank @@
+Normal rank
@@ Property / cites work @@
+Spanners and emulators with sublinear distance errors
+Normal rank