Chao Liao

collaborators

2 papers

cs.DS2022

Survivable Network Design Revisited: Group-Connectivity

Qingyun Chen, Bundit Laekhanukit, Chao Liao +1

In the classical survivable network design problem (SNDP), we are given an undirected graph $G = (V, E)$ with costs on edges and a connectivity requirement $k (s, t)$ for each pair of v…

cs.DS2022

Almost Tight Approximation Hardness for Single-Source Directed k-Edge-Connectivity

Chao Liao, Qingyun Chen, Bundit Laekhanukit +1

In the $k$ -connected directed Steiner tree problem ( $k$ -DST), we are given an $n$ -vertex directed graph $G = (V, E)$ with edge costs, a connectivity requirement $k$ , a root $r \in V$ a…