An improved parameterized algorithm for the minimum node multiway cut problem Conference Paper uri icon

abstract

  • 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(4knO(1)) time algorithm for this problem, significantly improving the previous algorithm of time 0(4k3nO(1)) for the problem. Our result also gives the first polynomial time algorithm for the MINIMUM NODE MULTIWAY CUT problem when the separator size is bounded by O(log n). Springer-Verlag Berlin Heidelberg 2007.

name of conference

  • Algorithms and Data Structures, 10th International Workshop, WADS 2007, Halifax, Canada, August 15-17, 2007, Proceedings

published proceedings

  • ALGORITHMS AND DATA STRUCTURES, PROCEEDINGS

author list (cited authors)

  • Chen, I., Liu, Y., & Lu, S.

complete list of authors

  • Chen, Iianer||Liu, Yang||Lu, Songjian

publication date

  • December 2007