Jenny Kaufmann

collaborators

3 papers

cs.DS2023

Approximating Min-Diameter: Standard and Bichromatic

Aaron Berger, Jenny Kaufmann, Virginia Vassilevska Williams

The min-diameter of a directed graph $G$ is a measure of the largest distance between nodes. It is equal to the maximum min-distance $d_{min} (u, v)$ across all pairs $u, v \in V (G)$ ,…

cs.DS2021

Approximation Algorithms for Min-Distance Problems in DAGs

Mina Dalirrooyfard, Jenny Kaufmann

The min-distance between two nodes $u, v$ is defined as the minimum of the distance from $v$ to $u$ or from $u$ to $v$ , and is a natural distance metric in DAGs. As with the standa…

math.CO2021

Coloring graph classes with no induced fork via perfect divisibility

T. Karthick, Jenny Kaufmann, Vaidy Sivaraman

For a graph $G$ , $χ (G)$ will denote its chromatic number, and $ω (G)$ its clique number. A graph $G$ is said to be perfectly divisible if for all induced subgraphs $H$ of $G$ , $V(H)…