Algorithms for Cut Problems on Trees

Iyad Kanj, Guohui Lin, Tian Liu +7

We study the {\sc multicut on trees} and the {\sc generalized multiway Cut on trees} problems. For the {\sc multicut on trees} problem, we present a parameterized algorithm that ru…