We study the multiobjective hypergraph min-cut problem: Given a hypergraph $H=(V,E)$ and $k$ cost functions $c_1, c_2, \ldots, c_k:E\to\mathbb{Z}_{\ge 0}$, the goal is to find a non-empty proper subset $U\subsetneq V$ of vertices with minimum $\max_{i\in [k]} c_i(\delta(U))$. When $k$ is part of input, the problem is N...
K. Chandrasekaran, Chandra Chekuri, Wei-Hao Zhu· 1 citation
We consider the Feedback Vertex Set problem (FVS): the input is an undirected graph $G=(V,E)$ and the goal is to find a minimum-cardinality (or a min-cost in the weighted case) subset $S \subseteq V$ of vertices such that $G-S$ has no cycles. A $2$-approximation via the local-ratio method was developed in the mid 90's...
K. Chandrasekaran, Chandra Chekuri, Shubhang Kulkarni· 0 citations
In the Steiner Point Removal problem, we are given a graph $G=(V,E)$ with an edge-length function $\ell_G: E\rightarrow \mathbb{R}_+$ and a subset $T\subseteq V$ of terminals. The goal is to find a minor $H=(T, E_H)$ of $G$ on vertex set $T$ such that the shortest path metric derived from $G$ on the edges of $H$ preser...
K. Chandrasekaran, Chandra Chekuri, Qing-Yun Chen et al.· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
