Iterative compression and exact algorithms

被引：26

作者：

Fomin, Fedor V. ^{[2
]}

Gaspers, Serge ^{[3
]}

Kratsch, Dieter ^{[4
]}

Liedloff, Mathieu ^{[1
]}

Saurabh, Saket ^{[5
]}

机构：

[1] Univ Orleans, Lab Informat Fondamentale Orleans, F-45067 Orleans 2, France

[2] Univ Bergen, Dept Informat, N-5020 Bergen, Norway

[3] Univ Chile, Ctr Modelamiento Matemat, Santiago 8370459, Chile

[4] Univ Paul Verlaine Metz, Lab Informat Theor & Appl, F-57045 Metz 01, France

[5] CIT Campus, Inst Math Sci, Madras 600113, Tamil Nadu, India

来源：

THEORETICAL COMPUTER SCIENCE | 2010年 / 411卷 / 7-9期

关键词：

Exponential time algorithms; Graph algorithms; Independent set; Hitting set; Induced cluster; Fixed parameter algorithms; Iterative compression; FEEDBACK VERTEX SET;

D O I：

10.1016/j.tcs.2009.11.012

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Iterative compression has recently led to a number of breakthroughs in parameterized complexity. Here, we show that the technique can also be useful in the design of exact exponential time algorithms to solve NP-hard problems. We exemplify our findings with algorithms for the MAXIMUM INDEPENDENT SET problem, a parameterized and a counting version of d-HITTING SET and the MAXIMUM INDUCED CLUSTER SUBGRAPH problem. (C) 2009 Elsevier B.V. All rights reserved.

引用

页码：1045 / 1053

页数：9

共 27 条

[1] Fourier Meets Mobius: Fast Subset Convolution [J].

Bjorklund, Andreas ;

Husfeldt, Thore ;

Kaski, Petteri ;

Koivisto, Mikko .

STOC 07: PROCEEDINGS OF THE 39TH ANNUAL ACM SYMPOSIUM ON THEORY OF COMPUTING, 2007, :67-74

[2]

Björklund A, 2006, ANN IEEE SYMP FOUND, P575

[3] Enumerating maximal independent sets with applications to graph colouring [J].

Byskov, JM .

OPERATIONS RESEARCH LETTERS, 2004, 32 (06) :547-556

[4] Improved algorithms for feedback vertex set problems [J].

Chen, Jianer ;

Fomin, Fedor V. ;

Liu, Yang ;

Lu, Songjian ;

Villanger, Yngve .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2008, 74 (07) :1188-1198

[5]

Chen J, 2006, LECT NOTES COMPUT SC, V4162, P238

[6] A Fixed-Parameter Algorithm for the Directed Feedback Vertex Set Problem [J].

Chen, Jianer ;

Liu, Yang ;

Lu, Songjian ;

O'Sullivan, Barry ;

Razgon, Igor .

JOURNAL OF THE ACM, 2008, 55 (05)

[7] An O(2O(k)n3) FPT algorithm for the undirected feedback vertex set problem [J].

Dehne, Frank ;

Fellows, Michael ;

Langston, Michael ;

Rosamond, Frances ;

Stevens, Kim .

THEORY OF COMPUTING SYSTEMS, 2007, 41 (03) :479-492

[8]

Dehne F, 2006, LECT NOTES COMPUT SC, V4169, P13

[9] THEORETICAL IMPROVEMENTS IN ALGORITHMIC EFFICIENCY FOR NETWORK FLOW PROBLEMS [J].

EDMONDS, J ;

KARP, RM .

JOURNAL OF THE ACM, 1972, 19 (02) :248-&

[10]

FELLOWS MR, 2007, P FCT 2007 FDN COMP, P312

← 1 2 3 →