6 papers · 1 filter
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…
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…
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…
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…
Low Sensitivity Hopsets
Vikrant Ashvinkumar, Aaron Bernstein, Chengyuan Deng +2
Given a weighted graph , a -hopset is an edge set such that for any , where can reach in , there is a path from to in $G \c…
Evaluating Stability in Massive Social Networks: Efficient Streaming Algorithms for Structural Balance
Vikrant Ashvinkumar, Sepehr Assadi, Chengyuan Deng +2
Structural balance theory studies stability in networks. Given a -vertex complete graph whose edges are labeled positive or negative, the graph is considered \emph{bal…