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