Improved parameterized algorithm for the multicut problem Academic Article

abstract

• The Multicut problem is for a given graph and a given collection of terminal pairs to find a vertex set of minimum size such that the two terminals in any pair are not connected after deletion of this vertex set. This problem is NP-hard. Based on the deep analysis of its structural characteristics, employing the strategy of set partition and the improved results of another related problem, this paper proposes a parameterized algorithm of running time O* for the problem, in which l denotes the number of terminal pairs and k denotes the number of removed vertices. This algorithm significantly improves the previous one of running time O*(2klkk4k3). by Institute of Software, the Chinese Academy of Sciences. All rights reserved.

authors

• Chen, Jianer

published proceedings

• Ruan Jian Xue Bao/Journal of Software

author list (cited authors)

• Liu, Y. L., Wang, J. X., & Chen, J. E.

complete list of authors

• Liu, YL||Wang, JX||Chen, JE

publication date

• July 2010

published in

• Ruanjian Xuebao  Journal

Digital Object Identifier (DOI)

• 10.3724/SP.J.1001.2010.03625

start page

• 1515

end page

• 1523

volume

• 21

issue

• 7