Fixed-parameter tractability

被引：27
作者：
Samer, Marko
Szeider, Stefan
机构：
来源：
Frontiers in Artificial Intelligence and Applications | 2009年 / 185卷 / 01期
关键词：
D O I：
10.3233/978-1-58603-929-5-425
中图分类号：
学科分类号：
摘要：
Parameterized complexity is a new theoretical framework that considers, in addition to the overall input size, the effects on computational complexity of a secondary measurement, the parameter. This two-dimensional viewpoint allows a fine-grained complexity analysis that takes structural properties of problem instances into account. The central notion is fixed-parameter tractability" which refers to solvability in polynomial time for each fixed value of the parameter such that the order of the polynomial time bound is independent of the parameter. This chapter presents main concepts and recent results on the parameterized complexity of the satisfiability problem and it outlines fundamental algorithmic ideas that arise in this context. Among the parameters considered are the size of backdoor sets with respect to various tractable base classes and the treewidth of graph representations of satisfiability instances. © 2009 John Franco and John Martin and IOS Press."
引用
收藏
页码：425 / 454
页数：29
相关论文
共 78 条
  • [11] Bodlaender H.L., Discovering treewidth, LNCS, 3381, pp. 1-16, (2005)
  • [12] Bacchus F., Winter J., Effective preprocessing with hyperresolution and equality reduction, LNCS, 2919, pp. 341-355, (2004)
  • [13] Cai L., Chen J., Downey R.G., Fellows M.R., Advice classes of parameterized tractability, Annals of Pure and Applied Logic, 84, 1, pp. 119-138, (1997)
  • [14] Crama Y., Ekin O., Hammer P.L., Variable and term removal from Boolean formulae, Discrete Applied Mathematics, 75, 3, pp. 217-230, (1997)
  • [15] Courcelle B., Engelfriet J., Rozenberg G., Handle-rewriting hypergraph grammars, Journal of Computer and System Sciences, 46, 2, pp. 218-270, (1993)
  • [16] Cesati M., Compendium of Parameterized Problems, (2006)
  • [17] Cohen D., Jeavons P., Gyssens M., A unified theory of structural tractability for constraint satisfaction problems, Journal of Computer and System Sciences, 74, 5, pp. 721-743, (2008)
  • [18] Chen J., Kanj I.A., Improved exact algorithms for MAX-SAT, Discrete Applied Mathematics, 142, 1-3, pp. 17-27, (2004)
  • [19] Chen J., Kanj I.A., Jia W., Vertex cover: Further observations and further improvements., Journal of Algorithms, 41, 2, pp. 280-301, (2001)
  • [20] Chen J., Kanj I.A., Xia G., Improved parameterized upper bounds for vertex cover., LNCS, 4162, pp. 238-249, (2006)
12345678