Motivated by non-uniform edge failures in network design, we introduce a multi-tier model of flexible graph connectivity. In k-tier Flexible Graph Connectivity (k-tier FGC), the input is an undirected graph G=(V, E) with non-negative edge costs, along with a classification of the edges into nested tiers T_1 subseteq T_...
K. Chandrasekaran, Raymond Jiang, Krishna Kalathur· 0 citations
A quasi-polynomial time approximation scheme (QPTAS) for hypergraph connectivity interdiction for hypergraph connectivity interdiction is obtained and AI tools were used to iterate and refine the algorithmic ideas underlying this work.
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.
