Showing cs.DSShow all
3 papers · 1 filter
cs.DS2026
Parallel Reachability and Shortest Paths on Non-sparse Digraphs: Near-linear Work and Sub-square-root Depth
Vikrant Ashvinkumar, Aaron Bernstein, Maximilian Probst Gutenberg +1
We present parallel algorithms for computing single-source reachability and shortest paths on directed -vertex -edge graphs using near-linear work and $o(\sqrt…
cs.DS2025
Vantage Point Selection Algorithms for Bottleneck Capacity Estimation
Vikrant Ashvinkumar, Rezaul Chowdhury, Jie Gao +3
Motivated by the problem of estimating bottleneck capacities on the Internet, we formulate and study the problem of vantage point selection. We are given a graph whose e…
cs.DS2024
Faster Approximation Algorithms for Restricted Shortest Paths in Directed Graphs
Vikrant Ashvinkumar, Aaron Bernstein, Adam Karczmarz
In the restricted shortest paths problem, we are given a graph whose edges are assigned two non-negative weights: lengths and delays, a source , and a delay threshold . T…