3 citations · 5 across the 10 of their papers we have counts for
4 papers · 1 filter
A Local-to-Global Theorem for Congested Shortest Paths
Shyan Akmal, Nicole Wein
Amiri and Wargalla (2020) proved the following local-to-global theorem in directed acyclic graphs (DAGs): if is a weighted DAG such that for each subset of 3 nodes there is…
Closing the Gap Between Directed Hopsets and Shortcut Sets
Aaron Bernstein, Nicole Wein
For an n-vertex directed graph , a -\emph{shortcut set} is a set of additional edges such that has the same transitive closure…
Approximation Algorithms and Hardness for -Pairs Shortest Paths and All-Nodes Shortest Cycles
Mina Dalirrooyfard, Ce Jin, Virginia Vassilevska Williams +1
We study the approximability of two related problems on graphs with nodes and edges: -Pairs Shortest Paths (-PSP), where the goal is to find a shortest path between $…
Online List Labeling: Breaking the Barrier
Michael A. Bender, Alex Conway, Martín Farach-Colton +3
The online list labeling problem is an algorithmic primitive with a large literature of upper bounds, lower bounds, and applications. The goal is to store a dynamically-changing se…