New bounds for approximating extremal distances in undirected graphs

DOI10.1137/1.9781611974331.CH27MaRDI QIDQ4575604zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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)

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

(17)

• scientific article; zbMATH DE number 7561539 (Why is no real title available?)
• On the L  ∞ -Norm of Extreme Points for Crossing Supermodular Directed Network LPs
• Near optimal bounds for the Erdős distinct distances problem in high dimensions
• Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems
• Towards tight approximation bounds for graph diameter and eccentricities
• Better approximation algorithms for the graph diameter
• Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter
• scientific article; zbMATH DE number 7561506 (Why is no real title available?)
• Tighter connections between Formula-SAT and shaving logs
• Fast approximation of eccentricities and distances in hyperbolic graphs
• Diameter, eccentricities and distance oracle computations on \(H\)-minor free graphs and graphs of bounded (distance) Vapnik-Chervonenkis dimension
• Extremal Distances in Directed Graphs: Tight Spanners and Near-Optimal Approximation Algorithms
• The Orthogonal Vectors Conjecture for Branching Programs and Formulas
• Toward Tight Approximation Bounds for Graph Diameter and Eccentricities
• A note on hardness of diameter approximation
• Parameterized complexity of diameter
• 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)