Showing 2026 · cs.DSShow all
2 papers · 2 filters
cs.DS2026
A Deterministic Near-Linear Time Approximation Algorithm for Restricted Shortest Paths in Directed Graphs
Vikrant Ashvinkumar
In the restricted shortest paths problem, we are given an -vertex -edge directed graph whose edges are assigned two non-negative weights (or resources) called lengths and…
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…