New bounds for approximating extremal distances in undirected graphs
DOI10.1137/1.9781611974331.CH27zbMATH Open1410.68396OpenAlexW4230677477MaRDI QIDQ4575604FDOQ4575604
Authors: Massimo Cairo, Roberto Grossi, Romeo Rizzi 
Publication date: 16 July 2018
Published in: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://hal.inria.fr/hal-01526665/file/soda2016.pdf
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
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Approximation algorithms (68W25) Distance in graphs (05C12)
Cited In (15)
- Title not available (Why is that?)
- 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
- Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter
- Toward Tight Approximation Bounds for Graph Diameter and Eccentricities
- Title not available (Why is that?)
- Fast approximation of eccentricities and distances in hyperbolic graphs
- Parameterized complexity of diameter
- Near optimal bounds for the Erdős distinct distances problem in high dimensions
- Diameter, Eccentricities and Distance Oracle Computations on H-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik–Chervonenkis Dimension
- Title not available (Why is that?)
- A note on hardness of diameter approximation
- Approximating the distance to properties in bounded-degree and general sparse graphs
- Extremal Distances in Directed Graphs: Tight Spanners and Near-Optimal Approximation Algorithms
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)
