3 citations · 5 across the 10 of their papers we have counts for
3 papers · 1 filter
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…
Improved Dynamic Graph Coloring
Shay Solomon, Nicole Wein
This paper studies the fundamental problem of graph coloring in fully dynamic graphs. Since the problem of computing an optimal coloring, or even approximating it to within $n^{1-ε…
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…