Parameterized complexity of cardinality constrained optimization problems

被引：52
作者：
Cai, Leizhen [1 ]
机构：
[1] Chinese Univ Hong Kong, Dept Comp Sci & Engn, Shatin, Hong Kong, Peoples R China
来源：
COMPUTER JOURNAL | 2008年 / 51卷 / 01期
关键词：
cardinality constrained optimization problem; exact algorithm; fixed-cardinality optimization problem; graph problem; parameterized complexity; FPT algorithm; W[1]-hardness;
D O I：
10.1093/comjnl/bxm086
中图分类号：
TP3 [计算技术、计算机技术];
学科分类号：
0812 ;
摘要：
We study the parameterized complexity of cardinality constrained optimization problems, i.e. optimization problems that require their solutions to contain specified numbers of elements to optimize solution values. For this purpose, we consider around 20 such optimization problems, as well as their parametric duals, that deal with various fundamental relations among vertices and edges in graphs. We have almost completely settled their parameterized complexity by giving either FPT algorithms or W[1]-hardness proofs. Furthermore, we obtain faster exact algorithms for several cardinality constrained optimization problems by transforming them into problems of finding maximum (minimum) weight triangles in weighted graphs.
引用
收藏
页码：102 / 121
页数：20
相关论文
共 22 条
  • [1] On the exponent of the all pairs shortest path problem
    Alon, N
    Galil, Z
    Margalit, O
    [J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1997, 54 (02) : 255 - 262
  • [2] COLOR-CODING
    ALON, N
    YUSTER, R
    ZWICK, U
    [J]. JOURNAL OF THE ASSOCIATION FOR COMPUTING MACHINERY, 1995, 42 (04): : 844 - 856
  • [3] [Anonymous], PARAMETERIZED COMPLE
  • [4] [Anonymous], PARAMETERIZED COMPLE
  • [5] Complexity of finding dense subgraphs
    Asahiro, Y
    Hassin, R
    Iwama, K
    [J]. DISCRETE APPLIED MATHEMATICS, 2002, 121 (1-3) : 15 - 26
  • [6] An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints
    Bruglieri, Maurizio
    Ehrgott, Matthias
    Hamacher, Horst W.
    Maffioli, Francesco
    [J]. DISCRETE APPLIED MATHEMATICS, 2006, 154 (09) : 1344 - 1357
  • [7] CAI L, 2007, LNCS, V4169, P239
  • [8] CAI L, 2007, UNPUB MAXIMUM K VERT
  • [9] CAI L, 2007, UNPUB FIXED PARAMETE
  • [10] CAI L, 2007, UNPUB EXACT FPT ALGO
123