Approximation algorithms for optimal hopsets
From MaRDI portal
Cites work
- A hierarchy of lower bounds for sublinear additive spanners
- A Randomized Parallel Algorithm for Single-Source Shortest Paths
- A simple efficient approximation scheme for the restricted shortest path problem
- Algorithms for hub label optimization
- Approximate distance oracles
- Approximating spanners and directed Steiner forest. Upper and lower bounds
- Approximating the norms of graph spanners
- Approximation algorithms for directed weighted spanners
- Approximation of Pareto Optima in Multiple-Objective, Shortest-Path Problems
- Approximation Schemes for the Restricted Shortest Path Problem
- Bridge girth: a unifying notion in network design
- Closing the gap between directed hopsets and shortcut sets
- Decremental single-source shortest paths on undirected graphs in near-linear total update time
- Deterministic Algorithms for Decremental Approximate Shortest Paths: Faster and Simpler
- Directed spanners via flow-based linear programs
- Dynamic algorithms for k-center on graphs
- Efficient construction of directed hopsets and parallel approximate shortest paths
- Everywhere-sparse spanners via dense subgraphs
- Fast approximate shortest paths in the congested clique
- Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms
- Folklore sampling is optimal for exact hopsets: confirming the \(\sqrt{n}\) barrier
- Generating Low-Degree 2-Spanners
- Generating Sparse 2-Spanners
- 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 2079397 (Why is no real title available?)
- Improved approximation algorithms for directed Steiner forest
- Improved approximation for the directed spanner problem
- Improved dynamic algorithms for maintaining approximate shortest paths under deletions
- Label Cover Instances with Large Girth and the Hardness of Approximating Basic k -Spanner
- Lasserre integrality gaps for graph spanners and related problems
- Lower bounds on sparse spanners, emulators, and diameter-reducing shortcuts
- Lowest-degree k-spanner: approximation and hardness
- Maximum flow and minimum-cost flow in almost-linear time
- Minimizing the diameter of a network using shortcut edges
- Multi-criteria approximation schemes for the resource constrained shortest path problem
- Near-optimal approximate decremental all pairs shortest paths
- Near-optimal distributed routing with low memory
- 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 separations and reductions for directed hopsets and preservers
- On sparse spanners of weighted graphs
- On the hardness of approximating spanners
- Online Directed Spanners and Steiner Forests.
- Parallel exact shortest paths in almost linear work and square root depth
- Parallel reachability in almost linear work and square root depth
- Polylog-time and near-linear work approximation scheme for undirected shortest paths
- Reachability and Distance Queries via 2-Hop Labels
- Reachability Preservers: New Extremal Bounds and Approximation Algorithms
- Set connectivity problems in undirected graphs and the directed Steiner network problem
- Simpler and higher lower bounds for shortcut sets
- The hardness of approximating spanner problems
- The network inhibition problem
- Thorup-Zwick emulators are universally optimal hopsets
- Towards bypassing lower bounds for graph shortcuts
This page was built for publication: Approximation algorithms for optimal hopsets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7363150)
