Toward Tight Approximation Bounds for Graph Diameter and Eccentricities
From MaRDI portal
Publication:5009785
DOI10.1137/18M1226737OpenAlexW3174842734MaRDI QIDQ5009785
Liam Roditty, Nicole Wein, Gilad Segal, Artūrs Bačkurs, Virginia Vassilevska Williams
Publication date: 6 August 2021
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/18m1226737
Analysis of algorithms and problem complexity (68Q25) Number-theoretic algorithms; complexity (11Y16) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items (2)
Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter ⋮ Parameterized complexity of diameter
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the all-pairs-shortest-path problem in unweighted undirected graphs.
- On sparse spanners of weighted graphs
- On the exponent of all pairs shortest path problem
- Which problems have strongly exponential complexity?
- A new approach to all-pairs shortest paths on real-weighted graphs
- Fast diameter and radius BFS-based computation in (weakly connected) real-world graphs
- A new algorithm for optimal 2-constraint satisfaction and its implications
- All-Pairs Small-Stretch Paths
- Approximate Distance Oracles with Improved Bounds
- Approximate distance oracles for unweighted graphs in expected O ( n 2 ) time
- On Approximate Distance Labels and Routing Schemes with Affine Stretch
- Undirected single-source shortest paths with positive integer weights in linear time
- Distributed Algorithms for Network Diameter and Girth
- Algorithmic Applications of Baur-Strassen’s Theorem
- Additive spanners and (α, β)-spanners
- All-pairs shortest paths for unweighted undirected graphs in o ( mn ) time
- Powers of tensors and fast matrix multiplication
- All pairs shortest paths using bridging sets and rectangular matrix multiplication
- Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
- An improved exponential-time algorithm for k -SAT
- Approximate distance oracles
- Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
- New Bounds for Approximating Extremal Distances in Undirected Graphs
- Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
- Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky
- All-Pairs Approximate Shortest Paths and Distance Oracle Preprocessing
- The 4/3 Additive Spanner Exponent Is Tight
- $(1 + \epsilon,\beta)$-Spanner Constructions for General Graphs
- FINDING k FARTHEST PAIRS AND k CLOSEST/FARTHEST BICHROMATIC PAIRS FOR POINTS IN THE PLANE
- All-Pairs Almost Shortest Paths
- Extremal Distances in Directed Graphs: Tight Spanners and Near-Optimal Approximation Algorithms
- Brief announcement
- Faster all-pairs shortest paths via circuit complexity
- A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs
- A Shortest Path Algorithm for Real-Weighted Undirected Graphs
- More Applications of the Polynomial Method to Algorithm Design
- Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
- Better Approximation Algorithms for the Graph Diameter
- Faster Algorithms for All-pairs Approximate Shortest Paths in Undirected Graphs
- Multiplying matrices faster than coppersmith-winograd
- Distance Oracles beyond the Thorup--Zwick Bound
- Fast approximation algorithms for the diameter and radius of sparse graphs
- New Additive Spanners
This page was built for publication: Toward Tight Approximation Bounds for Graph Diameter and Eccentricities
