MULTIVARIATE ALGORITHMICS FOR NP-HARD STRING PROBLEMS

被引：0
|
作者：
Bulteau, Laurent [1 ]
Hueffner, Falk [1 ]
Komusiewicz, Christian [1 ]
Niedermeier, Rolf [1 ]
机构：
[1] TU Berlin, Inst Softwaretech & Theoret Informat, Berlin, Germany
来源：
BULLETIN OF THE EUROPEAN ASSOCIATION FOR THEORETICAL COMPUTER SCIENCE | 2014年 / 114期
关键词：
D O I：
暂无
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
String problems arise in various applications ranging from text mining to biological sequence analysis. Many string problems are NP-hard. This motivates the search for (fixed-parameter) tractable special cases of these problems. We survey parameterized and multivariate algorithmics results for NP-hard string problems and identify challenges for future research.
引用
收藏
页码：32 / 73
页数：42
相关论文
共 50 条
  • [1] The string barcoding problem is NP-hard
    Dalpasso, M
    Lancia, G
    Rizzi, R
    COMPARATIVE GENOMICS, 2005, 3678 : 88 - 96
  • [2] The Multivariate Resultant Is NP-hard in Any Characteristic
    Grenet, Bruno
    Koiran, Pascal
    Portier, Natacha
    MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2010, 2010, 6281 : 477 - 488
  • [3] DECOMPOSITION OF ARITHMETICAL NP-HARD PROBLEMS
    MEJZLIK, P
    INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 1993, 48 (1-2) : 31 - 38
  • [4] Most Tensor Problems Are NP-Hard
    Hillar, Christopher J.
    Lim, Lek-Heng
    JOURNAL OF THE ACM, 2013, 60 (06)
  • [5] POLYNOMIAL BOUNDING FOR NP-HARD PROBLEMS
    CAMERINI, PM
    MAFFIOLI, F
    MATHEMATICAL PROGRAMMING STUDY, 1980, 12 (APR): : 115 - 119
  • [6] Dynamic Programming for NP-Hard Problems
    Wang, Xiaodong
    Tian, Jun
    CEIS 2011, 2011, 15
  • [7] The Fault Tolerance of NP-Hard Problems
    Glasser, Christian
    Pavan, A.
    Travers, Stephen
    LANGUAGE AND AUTOMATA THEORY AND APPLICATIONS, 2009, 5457 : 374 - +
  • [8] The fault tolerance of NP-hard problems
    Glasser, Christian
    Pavan, A.
    Travers, Stephen
    INFORMATION AND COMPUTATION, 2011, 209 (03) : 443 - 455
  • [9] NP-HARD MODULE ROTATION PROBLEMS
    AHN, K
    SAHNI, S
    IEEE TRANSACTIONS ON COMPUTERS, 1993, 42 (12) : 1506 - 1510
  • [10] STRING GRAPHS .2. RECOGNIZING STRING GRAPHS IS NP-HARD
    KRATOCHVIL, J
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 1991, 52 (01) : 67 - 78
12345