Fixed-parameter tractability results for feedback set problems in tournaments

被引：0

作者：

Dom, Michael ^{[1
]}

Guo, Jiong ^{[1
]}

Hueffner, Falk ^{[1
]}

Niedermeier, Rolf ^{[1
]}

Truss, Anke ^{[1
]}

机构：

[1] Univ Jena, Inst Informat, D-07743 Jena, Germany

来源：

ALGORITHMS AND COMPLEXITY, PROCEEDINGS | 2006年 / 3998卷

关键词：

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Complementing recent progress on classical complexity and polynomial-time approximability of feedback set problems in (bipartite) tournaments, we extend and partially improve fixed-parameter tractability results for these problems. We show that FEEDBACK VERTEX SET in tournaments is amenable to the novel iterative compression technique. Moreover, we provide data reductions and problem kernels for FEEDBACK VERTEX SET and FEEDBACK ARC SET in tournaments, and a depth-bounded search tree for FEEDBACK ARC SET in bipartite tournaments based on a new forbidden subgraph characterization.

引用

页码：320 / 331

页数：12

共 20 条

[1]

Ailon Nir, 2005, P 37 ANN ACM S THEOR, P684, DOI [10.1145/1060590.1060692, DOI 10.1145/1060590.1060692]

[2] Ranking tournaments [J].

Alon, N .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2006, 20 (01) :137-142

[3]

[Anonymous], PARAMETERIZED COMPLE

[4]

[Anonymous], PARAMETERIZED COMPLE

[5] A min-max theorem on feedback vertex sets [J].

Cai, MC ;

Deng, XT ;

Zang, WN .

MATHEMATICS OF OPERATIONS RESEARCH, 2002, 27 (02) :361-371

[6] An approximation algorithm or feedback vertex sets in tournaments [J].

Cai, MC ;

Deng, XT ;

Zang, WN .

SIAM JOURNAL ON COMPUTING, 2001, 30 (06) :1993-2007

[7]

CHARBIT P, 2005, IN PRESS COMBINATORI

[8]

CONITZER V, 2005, RC23748 IBM TJ WATS

[9]

Dehne F, 2005, LECT NOTES COMPUT SC, V3595, P859, DOI 10.1007/11533719_87

[10]

Fernau H., 2004, EL C COMP COMPL

← 1 2 →