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
(46)- Computing graph distances parameterized by treewidth and diameter
- Better approximations of non-Hamiltonian graphs
- Towards tight approximation bounds for graph diameter and eccentricities
- scientific article; zbMATH DE number 7561539 (Why is no real title available?)
- Faster Approximation Algorithms for Computing Shortest Cycles on Weighted Graphs
- Approximate proof-labeling schemes
- The complexity of diameter on H-free graphs
- Approximating all-points furthest pairs and maximum spanning trees in metric spaces
- scientific article; zbMATH DE number 7561542 (Why is no real title available?)
- Fast approximation algorithms for the diameter and radius of sparse graphs
- Diameter, eccentricities and distance oracle computations on H-minor free graphs and graphs of bounded (distance) Vapnik-Chervonenkis dimension
- New bounds for approximating extremal distances in undirected graphs
- Subquadratic-time algorithm for the diameter and all eccentricities on median graphs
- The complexity of diameter on \(H\)-free graphs
- _i-metric graphs: radius, diameter and all eccentricities
- On Approximating the d-Girth of a Graph
- Algorithms for diameters of unicycle graphs and diameter-optimally augmenting trees
- On the complexity of computing treebreadth
- A new application of orthogonal range searching for computing giant graph diameters
- Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems
- 4 vs 7 Sparse Undirected Unweighted Diameter Is SETH-hard at Time n 4/3
- Inapproximability of diameter in super-linear time: beyond the 5/3 ratio
- Approximating the Diameter of Planar Graphs in Near Linear Time
- Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter
- Toward Tight Approximation Bounds for Graph Diameter and Eccentricities
- A faster diameter problem algorithm for a chordal graph, with a connection to its center problem
- 4 vs 7 sparse undirected unweighted diameter is SETH-hard at time \(n^{4/3}\)
- Approximation algorithms for min-distance problems in DAGs
- Formally verified algorithms for upper-bounding state space diameters
- Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
- scientific article; zbMATH DE number 7561506 (Why is no real title available?)
- Towards hardness of approximation for polynomial time problems
- Fast approximation of eccentricities and distances in hyperbolic graphs
- Hardness of approximate diameter: now for undirected graphs
- Better diameter algorithms for bounded VC-dimension graphs and geometric intersection graphs
- Computing giant graph diameters
- Fast diameter and radius BFS-based computation in (weakly connected) real-world graphs
- Certificates in P and subquadratic-time computation of radius, diameter, and all eccentricities in graphs
- Fast approximate shortest paths in the congested clique
- Multivariate analysis of orthogonal range searching and graph distances
- $$\alpha _i$$-Metric Graphs: Radius, Diameter and all Eccentricities
- Linear-time graph distance and diameter approximation
- Faster Approximation of Distances in Graphs
- A note on hardness of diameter approximation
- Fast and Simple Approximation of the Diameter and Radius of a Graph
- Succinct enumeration of distant vertex pairs
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)
