49 citations · 193 across the 39 of their papers we have counts for
9 papers · 1 filter
Isometric Hamming embeddings of weighted graphs
Joseph Berleant, Kristin Sheridan, Anne Condon +2
A mapping from the vertex set of one graph to another graph is an isometric embedding if the shortest path distance between any two vertices in equal…
Factorization and pseudofactorization of weighted graphs
Kristin Sheridan, Joseph Berleant, Mark Bathe +2
For unweighted graphs, finding isometric embeddings is closely related to decompositions of into Cartesian products of smaller graphs. When is isomorphic to a Cartesian gra…
Better Lower Bounds for Shortcut Sets and Additive Spanners via an Improved Alternation Product
Kevin Lu, Virginia Vassilevska Williams, Nicole Wein +1
We obtain improved lower bounds for additive spanners, additive emulators, and diameter-reducing shortcut sets. Spanners and emulators are sparse graphs that approximately preserve…
Hardness of Approximate Diameter: Now for Undirected Graphs
Mina Dalirrooyfard, Ray Li, Virginia Vassilevska Williams
Approximating the graph diameter is a basic task of both theoretical and practical interest. A simple folklore algorithm can output a 2-approximation to the diameter in linear time…
Improved Approximation for Longest Common Subsequence over Small Alphabets
Shyan Akmal, Virginia Vassilevska Williams
This paper investigates the approximability of the Longest Common Subsequence (LCS) problem. The fastest algorithm for solving the LCS problem exactly runs in essentially quadratic…
Faster Monotone Min-Plus Product, Range Mode, and Single Source Replacement Paths
Yuzhou Gu, Adam Polak, Virginia Vassilevska Williams +1
One of the most basic graph problems, All-Pairs Shortest Paths (APSP) is known to be solvable in time, and it is widely open whether it has an time algori…