Better approximation algorithms for the graph diameter
From MaRDI portal
Recommendations
- Fast approximation algorithms for the diameter and radius of sparse graphs
- Toward Tight Approximation Bounds for Graph Diameter and Eccentricities
- Towards tight approximation bounds for graph diameter and eccentricities
- Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
- New bounds for approximating extremal distances in undirected graphs
Cited in
(49)- Better approximations of non-Hamiltonian graphs
- Formally verified algorithms for upper-bounding state space diameters
- A note on hardness of diameter approximation
- On the complexity of computing treebreadth
- Fast approximate shortest paths in the congested clique
- Fast diameter and radius BFS-based computation in (weakly connected) real-world graphs
- A faster diameter problem algorithm for a chordal graph, with a connection to its center problem
- Computing giant graph diameters
- Linear-time graph distance and diameter approximation
- On Approximating the d-Girth of a Graph
- Faster Approximation of Distances in Graphs
- 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
- Computing graph distances parameterized by treewidth and diameter
- Towards hardness of approximation for polynomial time problems
- Approximating the Diameter of Planar Graphs in Near Linear Time
- Fast approximation of eccentricities and distances in hyperbolic graphs
- Faster Approximation Algorithms for Computing Shortest Cycles on Weighted Graphs
- Toward Tight Approximation Bounds for Graph Diameter and Eccentricities
- Diameter, eccentricities and distance oracle computations on H-minor free graphs and graphs of bounded (distance) Vapnik-Chervonenkis dimension
- Algorithms and hardness for diameter in dynamic graphs
- Approximation algorithms for min-distance problems
- Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems
- Faster approximation algorithms for computing shortest cycles on weighted graphs
- Succinct enumeration of distant vertex pairs
- Towards tight approximation bounds for graph diameter and eccentricities
- Fast and Simple Approximation of the Diameter and Radius of a Graph
- Fast approximation algorithms for the diameter and radius of sparse graphs
- Approximate proof-labeling schemes
- Algorithms for diameters of unicycle graphs and diameter-optimally augmenting trees
- Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter
- 4 vs 7 Sparse Undirected Unweighted Diameter Is SETH-hard at Time n 4/3
- Subquadratic-time algorithm for the diameter and all eccentricities on median graphs
- $$\alpha _i$$-Metric Graphs: Radius, Diameter and all Eccentricities
- Approximating all-points furthest pairs and maximum spanning trees in metric spaces
- _i-metric graphs: radius, diameter and all eccentricities
- A new application of orthogonal range searching for computing giant graph diameters
- Hardness of approximate diameter: now for undirected graphs
- Certificates in P and subquadratic-time computation of radius, diameter, and all eccentricities in graphs
- The complexity of diameter on H-free graphs
- The complexity of diameter on \(H\)-free graphs
- Inapproximability of diameter in super-linear time: beyond the 5/3 ratio
- 4 vs 7 sparse undirected unweighted diameter is SETH-hard at time \(n^{4/3}\)
- Approximation algorithms for min-distance problems in DAGs
- Better diameter algorithms for bounded VC-dimension graphs and geometric intersection graphs
- Fault-tolerant ST-diameter oracles
- Shortest paths in multimode graphs
- Multivariate analysis of orthogonal range searching and graph distances
This page was built for publication: Better approximation algorithms for the graph diameter
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5384040)
