An Improved Parameterized Algorithm for the Minimum Node Multiway Cut Problem

被引：134

作者：

Chen, Jianer ^{[1
]}

Liu, Yang ^{[1
]}

Lu, Songjian ^{[1
]}

机构：

[1] Texas A&M Univ, Dept Comp Sci, College Stn, TX 77843 USA

来源：

ALGORITHMICA | 2009年 / 55卷 / 01期

基金：

美国国家科学基金会;

关键词：

Multiway cut problem; Parameterized algorithm; Fixed-parameter tractability; Minimum cut; Network flow;

D O I：

10.1007/s00453-007-9130-6

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

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(4k(3)n(5)) 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).

引用

页码：1 / 13

页数：13

共 15 条

[1] Markov random fields with efficient approximations [J].

Boykov, Y ;

Veksler, O ;

Zabih, R .

1998 IEEE COMPUTER SOCIETY CONFERENCE ON COMPUTER VISION AND PATTERN RECOGNITION, PROCEEDINGS, 1998, :648-655

[2] An improved approximation algorithm for multiway cut [J].

Calinescu, G ;

Karloff, H .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2000, 60 (03) :564-574

[3]

CHARTRAND G, 1986, WADSWORTH COLE MATH

[4]

CHEN J, 2007, FIXED PARAMETE UNPUB

[5]

Cunningham W., 1991, DIMACS SERIES DISCRE, V5, P105

[6] THE COMPLEXITY OF MULTITERMINAL CUTS [J].

DAHLHAUS, E ;

JOHNSON, DS ;

PAPADIMITRIOOU, CH ;

SEYMOUR, PD ;

YANNAKAKIS, M .

SIAM JOURNAL ON COMPUTING, 1994, 23 (04) :864-894

[7]

DOWNEY R, 1999, MONOGRAPH COMPUTER S

[8] FIXED-PARAMETER TRACTABILITY AND COMPLETENESS .1. BASIC RESULTS [J].

DOWNEY, RG ;

FELLOWS, MR .

SIAM JOURNAL ON COMPUTING, 1995, 24 (04) :873-921

[9]

Ford L. R., 1962, FLOWS NETWORKS

[10]

Karger D. R., 1999, Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, P668, DOI 10.1145/301250.301430

← 1 2 →