Rajesh Chitnis

activity

20142024

most citedParameterized Streaming Algorithms for Vertex Cover

2 citations · 3 across the 3 of their papers we have counts for

collaborators

3 papers

cs.DS2024★ 1 cited

Lower Bounds for Approximate (& Exact) k-Disjoint-Shortest-Paths

Rajesh Chitnis, Samuel Thomas, Anthony Wirth

Given a graph $G = (V, E)$ and a set $T = {(s_{i}, t_{i}) : 1 \leq i \leq k} \subseteq V \times V$ of $k$ pairs, the $k$ -vertex-disjoint-paths (resp. $k$ -edge-disjoint-paths) problem asks t…

cs.DS2023

Sublinear-Space Streaming Algorithms for Estimating Graph Parameters on Sparse Graphs

Xiuge Chen, Rajesh Chitnis, Patrick Eades +1

In this paper, we design sub-linear space streaming algorithms for estimating three fundamental parameters -- maximum independent set, minimum dominating set and maximum matching -…

cs.DS2014★ 2 cited

Parameterized Streaming Algorithms for Vertex Cover

Rajesh Chitnis, Graham Cormode, MohammadTaghi Hajiaghayi +1

As graphs continue to grow in size, we seek ways to effectively process such data at scale. The model of streaming graph processing, in which a compact summary is maintained as eac…