Approximation algorithms for min-distance problems

DOI10.4230/LIPICS.ICALP.2019.46MaRDI QIDQ5091199FDOQ5091199

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

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

zbMATH Keywords

diametergraph algorithmsradiuseccentricitiesfine-grained complexity

Mathematics Subject Classification ID

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

Cites Work

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

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)