2 citations · 4 across the 7 of their papers we have counts for
10 papers
Length-Constrained Network Design in Planar Digraphs
Chandra Chekuri, Rhea Jain
We study length-constrained generalizations of Directed Steiner Tree (DST) and Directed Steiner Forest (DSF) in planar digraphs. In both problems, the input is a directed graph wit…
Node-Weighted Multicut in Planar Digraphs
Chandra Chekuri, Rhea Jain
Kawarabayashi and Sidiropoulos [KS22] obtained an -approximation algorithm for Multicut in planar digraphs via a natural LP relaxation, which also establishes a corres…
Streaming Algorithms for Network Design
Chandra Chekuri, Rhea Jain, Sepideh Mahabadi +1
We consider the Survivable Network Design problem (SNDP) in the single-pass insertion-only streaming model. The input to SNDP is an edge-weighted graph and an integer…
A Polylogarithmic Approximation for Directed Steiner Forest in Planar Digraphs
Chandra Chekuri, Rhea Jain
We consider Directed Steiner Forest (DSF), a fundamental problem in network design. The input to DSF is a directed edge-weighted graph and a collection of vertex pairs…
From Directed Steiner Tree to Directed Polymatroid Steiner Tree in Planar Graphs
Chandra Chekuri, Rhea Jain, Shubhang Kulkarni +2
In the Directed Steiner Tree (DST) problem the input is a directed edge-weighted graph , a root vertex and a set of terminals. The goal is to find…
Exponential Time Approximation for Coloring 3-Colorable Graphs
Venkatesan Guruswami, Rhea Jain
The problem of efficiently coloring -colorable graphs with few colors has received much attention on both the algorithmic and inapproximability fronts. We consider exponential t…
Approximation Algorithms for Hop Constrained and Buy-at-Bulk Network Design via Hop Constrained Oblivious Routing
Chandra Chekuri, Rhea Jain
We consider two-cost network design models in which edges of the input graph have an associated cost and length. We build upon recent advances in hop-constrained oblivious routing…
Approximation Algorithms for Network Design in Non-Uniform Fault Models
Chandra Chekuri, Rhea Jain
The Survivable Network Design problem (SNDP) is a well-studied problem, motivated by the design of networks that are robust to faults under the assumption that any subset of edges…
Approximating Flexible Graph Connectivity via Räcke Tree based Rounding
Chandra Chekuri, Rhea Jain
Flexible graph connectivity is a new network design model introduced by Adjiashvili. It has seen several recent algorithmic advances. Despite these, the approximability even in the…
Augmentation based Approximation Algorithms for Flexible Network Design
Chandra Chekuri, Rhea Jain
Adjiashvili introduced network design in a non-uniform fault model: the edge set of a given graph is partitioned into safe and unsafe edges. A vertex pair is -flex-c…