首页    期刊浏览 2024年11月24日 星期日
登录注册

文章基本信息

  • 标题:Algorithmic Meta-Theorems
  • 本地全文:下载
  • 作者:Stephan Kreutzer
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2009
  • 卷号:2009
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    Algorithmic meta-theorems are general algorithmic results applying to a whole range of problems, rather than just to a single problem alone. They often have a logical and astructural component, that is they are results of the form:"every computational problem that can be formalised in a given logic L can be solved efficiently on every class C of structures satisfying certain conditions."This paper gives a survey of algorithmic meta-theorems obtained in recent years and the methods used to prove them. As many meta-theorems use results from graph minor theory, we give a brief introduction to the theory developed by Robertson and Seymour for their proof of the graph minor theorem and state the main algorithmic consequences of this theory as far as they are needed for the theory of algorithmic meta-theorems.

  • 关键词:algorithmic graph theory; logic and complexity; Parameterized Complexity
国家哲学社会科学文献中心版权所有