Showing cs.DSShow all
2 papers · 1 filter
cs.DS2026
An \(O(\log n)\)-Approximation for Three-Terminal Reachability-Preserving Minimum Edge Cut
Qi Duan
In the three-terminal Reachability-Preserving Minimum Edge Cut problem, the input is an undirected edge-weighted graph with terminals \(s_1,s_2,t\). The objective is to delete a mi…
cs.DS2026
Threshold Minimum Cut with Terminal Quotas: Logarithmic and Planar Approximation Algorithms
Qi Duan
We study threshold minimum cut problems with a distinguished root vertex, a set of terminals, and a quota. In the threshold minimum edge cut problem (\TMEC), the goal is to find a…