Approximation algorithms for min-distance problems

DOI10.4230/LIPICS.ICALP.2019.46MaRDI QIDQ5091199zbMATH OpenFDO

Authors M. Dalirrooyfard, Nikhil Vyas, Nicole Wein, Yinzhan Xu, Yuancheng Yu, Virginia Vassilevska Williams

Publication date 21 July 2022

Full work available at URL https://arxiv.org/abs/1904.11606

zbMATH Keywords

diametergraph algorithmsradiuseccentricitiesfine-grained complexity

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Recommendations

• Fast approximation algorithms for the diameter and radius of sparse graphs
• Better approximation algorithms for the graph diameter
• Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
• Faster Approximation of Distances in Graphs
• Towards tight approximation bounds for graph diameter and eccentricities

Cites work

• scientific article; zbMATH DE number 4137792 (Why is no real title available?)
• scientific article; zbMATH DE number 1305501 (Why is no real title available?)
• scientific article; zbMATH DE number 2086613 (Why is no real title available?)
• scientific article; zbMATH DE number 2119682 (Why is no real title available?)
• A Shortest Path Algorithm for Real-Weighted Undirected Graphs
• All-pairs shortest paths for unweighted undirected graphs in \(o(mn)\) time
• Approximating the diameter of planar graphs in near linear time
• Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
• Better approximation algorithms for the graph diameter
• Diameter determination on restricted graph families
• Efficient algorithms for center problems in cactus networks
• Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
• Fast approximation algorithms for the diameter and radius of sparse graphs
• Fast diameter and radius BFS-based computation in (weakly connected) real-world graphs
• Faster Approximation of Distances in Graphs
• Faster all-pairs shortest paths via circuit complexity
• Networks cannot compute their diameter in sublinear time
• New bounds for approximating extremal distances in undirected graphs
• Optimum Locations of Switching Centers and the Absolute Centers and Medians of a Graph
• Subcubic equivalences between graph centrality problems, APSP and diameter
• Subgraph Isomorphism in Planar Graphs and Related Problems
• The absolute center of a network
• Towards tight approximation bounds for graph diameter and eccentricities

Cited in

(2)

• Approximating Minimization Diagrams and Generalized Proximity Search
• A Deterministic Reduction for the Gap Minimum Distance Problem

This page was built for publication: Approximation algorithms for min-distance problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5091199)