An improved parameterized algorithm for the minimum node mutiway cut problem

Chen J, Liu Y, Lu S. An improved parameterized algorithm for the minimum node mutiway cut problem. Algorithmica. 2009:55(1):1-13.

The parameterized node multiway cut problem is for a given graph to find a separator of size bounded by k whose removal separates a collection of terminal sets in the graph. In this paper, we develop an O(k4 k n 3) time algorithm for this problem, significantly improving the previous algorithm of time O(4k3n5)O(4k3n5) for the problem. Our result gives the first polynomial time algorithm for the minimum node multiway cut problem when the separator size is bounded by O(log n).

Publication Year: 
2009
Faculty Author: 
Publication Credits: 
Chen J, Liu Y, Lu S
Publication Download: 
AttachmentSize
PDF icon AnImprovedParameterized.pdf319.16 KB
^