Showing 2024Show all
2 papers · 1 filter
cs.DS2024
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…
cs.DS2024
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…