Showing cs.DSShow all
2 papers · 1 filter
cs.DS2024
Fine-Grained Optimality of Partially Dynamic Shortest Paths and More
Barna Saha, Virginia Vassilevska Williams, Yinzhan Xu +1
Single Source Shortest Paths () is among the most well-studied problems in computer science. In the incremental (resp. decremental) setting, the goal is to maintain…
cs.DS2023
Faster Approximate All Pairs Shortest Paths
Barna Saha, Christopher Ye
The all pairs shortest path problem (APSP) is one of the foundational problems in computer science. For weighted dense graphs on vertices, no truly sub-cubic algorithms exist t…