13 citations · 40 across the 13 of their papers we have counts for
19 papers
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 -…
Tight Lower Bounds for Approximate & Exact -Center in
Rajesh Chitnis, Nitin Saurabh
In the discrete -center problem, we are given a metric space where and the goal is to select a set of centers which minimizes the…
A Tight Lower Bound for Edge-Disjoint Paths on Planar DAGs
Rajesh Chitnis
(see paper for full abstract) We show that the Edge-Disjoint Paths problem is W[1]-hard parameterized by the number of terminal pairs, even when the input graph is a planar dir…
Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions)
Rajesh Chitnis, Andreas Emil Feldmann, MohammadTaghi Hajiaghayi +1
(see paper for full abstract) Given a vertex-weighted directed graph and a set of terminals, the objective of the SCSS problem is to find…
Towards a Theory of Parameterized Streaming Algorithms
Rajesh Chitnis, Graham Cormode
Parameterized complexity attempts to give a more fine-grained analysis of the complexity of problems: instead of measuring the running time as a function of only the input size, we…
FPT Inapproximability of Directed Cut and Connectivity Problems
Rajesh Chitnis, Andreas Emil Feldmann
(see paper for full abstract) Cut problems and connectivity problems on digraphs are two well-studied classes of problems from the viewpoint of parameterized complexity. After a se…