New bounds for approximating extremal distances in undirected graphs
From MaRDI portal
(Redirected from Publication:4575604)
Recommendations
- Towards tight approximation bounds for graph diameter and eccentricities
- Toward Tight Approximation Bounds for Graph Diameter and Eccentricities
- Better approximation algorithms for the graph diameter
- Fast approximation algorithms for the diameter and radius of sparse graphs
- Computing graph distances parameterized by treewidth and diameter
Cited in
(23)- Extremal Distances in Directed Graphs: Tight Spanners and Near-Optimal Approximation Algorithms
- Towards tight approximation bounds for graph diameter and eccentricities
- scientific article; zbMATH DE number 7561539 (Why is no real title available?)
- Better approximation algorithms for the graph diameter
- Tighter connections between Formula-SAT and shaving logs
- Diameter, eccentricities and distance oracle computations on H-minor free graphs and graphs of bounded (distance) Vapnik-Chervonenkis dimension
- On the L ∞ -Norm of Extreme Points for Crossing Supermodular Directed Network LPs
- The Orthogonal Vectors Conjecture for Branching Programs and Formulas
- Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems
- Inapproximability of diameter in super-linear time: beyond the 5/3 ratio
- Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter
- Distributed distance approximation
- Toward Tight Approximation Bounds for Graph Diameter and Eccentricities
- 4 vs 7 sparse undirected unweighted diameter is SETH-hard at time \(n^{4/3}\)
- scientific article; zbMATH DE number 7561506 (Why is no real title available?)
- Fast approximation of eccentricities and distances in hyperbolic graphs
- Hardness of approximate diameter: now for undirected graphs
- Near optimal bounds for the Erdős distinct distances problem in high dimensions
- Better diameter algorithms for bounded VC-dimension graphs and geometric intersection graphs
- Parameterized complexity of diameter
- Certificates in P and subquadratic-time computation of radius, diameter, and all eccentricities in graphs
- A note on hardness of diameter approximation
- Approximating the distance to properties in bounded-degree and general sparse graphs
This page was built for publication: New bounds for approximating extremal distances in undirected graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575604)
