7 papers · 1 filter
On Diameter Approximation in Directed Graphs
Amir Abboud, Mina Dalirrooyfard, Ray Li +1
Computing the diameter of a graph, i.e. the largest distance, is a fundamental problem that is central in fine-grained complexity. In undirected graphs, the Strong Exponential Time…
Towards Optimal Output-Sensitive Clique Listing or: Listing Cliques from Smaller Cliques
Mina Dalirrooyfard, Surya Mathialagan, Virginia Vassilevska Williams +1
We study finding and listing -cliques in a graph, for constant , a fundamental problem of both theoretical and practical importance. Our main contribution is a new outp…
Approximation Algorithms for Min-Distance Problems in DAGs
Mina Dalirrooyfard, Jenny Kaufmann
The min-distance between two nodes is defined as the minimum of the distance from to or from to , and is a natural distance metric in DAGs. As with the standa…
Tight Conditional Lower Bounds for Approximating Diameter in Directed Graphs
Mina Dalirrooyfard, Nicole Wein
Among the most fundamental graph parameters is the Diameter, the largest distance between any pair of vertices. Computing the Diameter of a graph with edges requires $m^{2-o(1)…
Conditionally optimal approximation algorithms for the girth of a directed graph
Mina Dalirrooyfard, Virginia Vassilevska Williams
It is known that a better than -approximation algorithm for the girth in dense directed unweighted graphs needs time unless one uses fast matrix multiplication. Mea…
Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems
Mina Dalirrooyfard, Virginia Vassilevska Williams, Nikhil Vyas +1
Some of the most fundamental and well-studied graph parameters are the Diameter (the largest shortest paths distance) and Radius (the smallest distance for which a "center" node ca…
Approximation Algorithms for Min-Distance Problems
Mina Dalirrooyfard, Virginia Vassilevska Williams, Nikhil Vyas +3
We study fundamental graph parameters such as the Diameter and Radius in directed graphs, when distances are measured using a somewhat unorthodox but natural measure: the distance…