Showing cs.CCShow all
2 papers · 1 filter
cs.CC2026
Three-Terminal Reachability-Preserving Minimum Node Cut: Planar Hardness and a General-Graph \(O(\sqrt n)\)-Approximation
Qi Duan
We study the three-terminal reachability-preserving minimum node cut problem (\RPMNC). The input is an undirected graph \(G=(V,E)\), nonnegative vertex weights on nonterminal verti…
cs.CC2026
A Polynomial-Time -Approximation for Undirected Three-Terminal Reachability-Preserving Minimum Edge Cut
Qi Duan
We study the undirected three-terminal reachability-preserving minimum edge cut problem. The input is an undirected graph with nonnegative edge costs, two protected termi…