9 citations · 21 across the 5 of their papers we have counts for
6 papers
Node-Weighted Network Design in Planar and Minor-Closed Families of Graphs
Chandra Chekuri, Alina Ene, Ali Vakilian
We consider node-weighted survivable network design (SNDP) in planar graphs and minor-closed families of graphs. The input consists of a node-weighted undirected graph an…
On Routing Disjoint Paths in Bounded Treewidth Graphs
Alina Ene, Matthias Mnich, Marcin Pilipczuk +1
We study the problem of routing on disjoint paths in bounded treewidth graphs with both edge and node capacities. The input consists of a capacitated graph and a collection of…
Connected Domatic Packings in Node-capacitated Graphs
Alina Ene, Nitish Korula, Ali Vakilian
A set of vertices in a graph is a dominating set if every vertex outside the set has a neighbor in the set. A dominating set is connected if the subgraph induced by its vertices is…
Approximation Algorithms for Submodular Multiway Partition
Chandra Chekuri, Alina Ene
We study algorithms for the Submodular Multiway Partition problem (SubMP). An instance of SubMP consists of a finite ground set , a subset of elements $S = \{s_1,s_2,...,s_k…
Submodular Cost Allocation Problem and Applications
Chandra Chekuri, Alina Ene
We study the Minimum Submodular-Cost Allocation problem (MSCA). In this problem we are given a finite ground set and non-negative submodular set functions o…
Prize-Collecting Steiner Tree and Forest in Planar Graphs
Chandra Chekuri, Alina Ene, Nitish Korula
We obtain polynomial-time approximation-preserving reductions (up to a factor of 1 + ε) from the prize-collecting Steiner tree and prize-collecting Steiner forest problems in plana…