2 citations · 4 across the 7 of their papers we have counts for
5 papers · 1 filter
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…