Low sensitivity hopsets
From MaRDI portal
Cites work
- A faster distributed single-source shortest paths algorithm
- A hierarchy of lower bounds for sublinear additive spanners
- A Randomized Parallel Algorithm for Single-Source Shortest Paths
- Beating matrix multiplication for \(n^{1/3}\)-directed shortcuts
- Better lower bounds for shortcut sets and additive spanners via an improved alternation product
- Brief Announcement
- Closing the gap between directed hopsets and shortcut sets
- Decremental SSSP in Weighted Digraphs: Faster and Against an Adaptive Adversary
- Differentially private all-pairs shortest path distances: improved algorithms and lower bounds
- Differentially private range query on shortest paths
- Efficient construction of directed hopsets and parallel approximate shortest paths
- Extremal problems in discrete geometry
- Fast Algorithms for Finding Nearest Common Ancestors
- Folklore sampling is optimal for exact hopsets: confirming the \(\sqrt{n}\) barrier
- Having hope in hops: new spanners, preservers and lower bounds for hopsets
- Hopsets with constant hopbound, and applications to approximate shortest paths
- scientific article; zbMATH DE number 512931 (Why is no real title available?)
- scientific article; zbMATH DE number 2079397 (Why is no real title available?)
- scientific article; zbMATH DE number 7788355 (Why is no real title available?)
- Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs
- Lower bounds on sparse spanners, emulators, and diameter-reducing shortcuts
- Near-optimal decremental SSSP in dense weighted digraphs
- Nearly work-efficient parallel algorithm for digraph reachability
- New (α, β) Spanners and Hopsets
- New diameter-reducing shortcuts and directed hopsets: breaking the \(O(\sqrt{n})\) barrier
- New results on linear size distance preservers
- On Sets of Integers Which Contain No Three Terms in Arithmetical Progression
- Parallel reachability in almost linear work and square root depth
- Path-reporting distance oracles with logarithmic stretch and linear size
- Path-reporting distance oracles with logarithmic stretch and size O(n n)
- Polylog-time and near-linear work approximation scheme for undirected shortest paths
- Simpler and higher lower bounds for shortcut sets
- Spanners and emulators with sublinear distance errors
- Sparse Sourcewise and Pairwise Distance Preservers
- Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs
- Testing subgraphs in large graphs
- The 4/3 additive spanner exponent is tight
- The algorithmic foundations of differential privacy
- The discrepancy of shortest paths
- Thorup-Zwick emulators are universally optimal hopsets
- Time–Work Tradeoffs of the Single-Source Shortest Paths Problem
This page was built for publication: Low sensitivity hopsets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7296643)
