Ariel Sapir

collaborators

2 papers

cs.DS2026

Weighted Emulators with Local Heaviest Edges Stretch for Undirected Graphs

Liam Roditty, Ariel Sapir

We introduce a generalized family of $\left( 2\cdot \left\lfloor \frac{k}{2} \right\rfloor-1, 2\cdot \left\lceil \frac{k}{2} \right\rceil \cdot W_{1} +\max\left\{0,2\cdot\left(\lef…

cs.DS2026

Additive, Near-Additive, and Multiplicative Approximations for APSP in Weighted Undirected Graphs: Trade-offs and Algorithms

Liam Roditty, Ariel Sapir

We present a $+ 2 \sum_{i = 1}^{k + 1} W_{i}$ -APASP algorithm for dense weighted graphs with runtime $O ~ (n^{2 + \frac{1}{3 k + 2}})$ , where $W_{i}$ is the weight of an $i^{th}…