Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems
From MaRDI portal
Publication:5091200
DOI10.4230/LIPIcs.ICALP.2019.47OpenAlexW2959518674MaRDI QIDQ5091200
Mina Dalirrooyfard, Nicole Wein, Nikhil Vyas, Virginia Vassilevska Williams
Publication date: 21 July 2022
Full work available at URL: https://arxiv.org/abs/1904.11601
Cites Work
- Unnamed Item
- Euclidean minimum spanning trees and bichromatic closest pairs
- Algorithms for bichromatic line-segment problems and polyhedral terrains
- New pairwise spanners
- A new approach to all-pairs shortest paths on real-weighted graphs
- A new algorithm for optimal 2-constraint satisfaction and its implications
- A subset spanner for Planar graphs, with application to subset TSP
- On Pairwise Spanners
- Distributed Algorithms for Network Diameter and Girth
- Sparse Sourcewise and Pairwise Distance Preservers
- More algorithms for all-pairs shortest paths in weighted graphs
- Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
- New Bounds for Approximating Extremal Distances in Undirected Graphs
- Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
- Completeness for First-Order Properties on Sparse Structures with Algorithmic Applications
- Extreme Distances in Multicolored Point Sets
- FINDING k FARTHEST PAIRS AND k CLOSEST/FARTHEST BICHROMATIC PAIRS FOR POINTS IN THE PLANE
- Towards tight approximation bounds for graph diameter and eccentricities
- A Shortest Path Algorithm for Real-Weighted Undirected Graphs
- Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
- Better Approximation Algorithms for the Graph Diameter
- Fast computation of empirically tight bounds for the diameter of massive graphs
- Fast approximation algorithms for the diameter and radius of sparse graphs
- On the complexity of \(k\)-SAT
This page was built for publication: Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems
