5 citations · 5 across the 8 of their papers we have counts for
Showing cs.DSShow all
3 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…
cs.DS2013
On the Connectivity Preserving Minimum Cut Problem
Qi Duan, Jinhui Xu
In this paper, we study a generalization of the classical minimum cut prob- lem, called Connectivity Preserving Minimum Cut (CPMC) problem, which seeks a minimum cut to separate a…