5 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…
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…