5 citations · 5 across the 8 of their papers we have counts for
4 papers · 1 filter
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…
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…
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…
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…