Simple and Improved Parameterized Algorithms for Multiterminal Cuts
Simple and Improved Parameterized Algorithms for Multiterminal Cuts
复制标题
DOI：
10.1007/s00224-009-9215-5
复制
发表时间：
2009-05
影响因子：
0.5
通讯作者：
Mingyu Xiao
中科院分区：
文献类型：
--
作者：
Mingyu Xiao
给定一个图形g =(V，E)，有顶点和顶点，以及一个叫做终端的子集合，边缘（分别是顶点）多终端切割问题是找到一组最多的边缘（非终端顶点），其从g中移除将每个终端与所有其他终端分开。这两个问题是NP-hard分叉≥3，但众所周知是流技术的多项式时间可解分叉=2。本文在最远最小隔离割的概念基础上，设计了几种简单改进的多端割算法。我们证明了边缘多终端切割可以在inO（2lkT(n,m)）时间内求解，顶点多终端切割可以在inO（klT(n,m)）时间内求解，其中et (n,m)=O（min (n2/3,m1/2)m）是在非加权图中寻找最小（s,t）切割的运行时间。此外，当k值较小时，我们的算法的运行时间界限可以进一步缩小：Edge 3-Terminal Cut可以在inO（1.415lT(n,m)）时间内求解，Vertex {3,4,5,6}-Terminal Cuts可以分别在inO（2.059lT(n,m)）、O（2.772lT(n,m)）、O（3.349lT(n,m)）和do （3.857lT(n,m)）时间内求解。我们在多终端切割上的结果也可以用来获得更快的算法formulticcut：边缘多切割的时间算法和顶点多切割的do (（2k)k+l/2T(n,m)）时间算法。
Given a graphG=(V,E) withnvertices andmedges, and a subsetTofkvertices calledterminals, theEdge(respectively,Vertex)Multiterminal Cutproblem is to find a set of at mostledges (non-terminal vertices), whose removal fromGseparates each terminal from all the others. These two problems are NP-hard fork≥3 but well-known to be polynomial-time solvable fork=2 by the flow technique. In this paper, based on a notionfarthest minimum isolating cut, we design several simple and improved algorithms for Multiterminal Cut. We show that Edge Multiterminal Cut can be solved inO(2lkT(n,m)) time and Vertex Multiterminal Cut can be solved inO(klT(n,m)) time, whereT(n,m)=O(min (n2/3,m1/2)m) is the running time of finding a minimum (s,t) cut in an unweighted graph. Furthermore, the running time bounds of our algorithms can be further reduced for small values ofk: Edge 3-Terminal Cut can be solved inO(1.415lT(n,m)) time, and Vertex {3,4,5,6}-Terminal Cuts can be solved inO(2.059lT(n,m)),O(2.772lT(n,m)),O(3.349lT(n,m)) andO(3.857lT(n,m)) time respectively. Our results on Multiterminal Cut can also be used to obtain faster algorithms forMulticut:-time algorithm for Edge Multicut andO((2k)k+l/2T(n,m))-time algorithm for Vertex Multicut.