参数复杂性在算法图论上的一些应用

项目名称： 参数复杂性在算法图论上的一些应用

项目编号： No.60970011

项目类型： 面上项目

立项/批准年度： 2010

项目学科： 自动化技术、计算机技术

项目作者： 陈翌佳

作者单位： 上海交通大学

项目金额： 30万元

中文摘要： 参数复杂性是算法复杂性理论的一个较新的分支。相对于经典理论，它主要处理二维计算问题，即问题的输入中有一部分较小的参数。参数复杂性理论的核心是固定参数算法，它允许算法的运行时间超过多项式，只要非多项式时间的行为是被局限在小参数上的。由于许多NP难的算法图论问题都是二维问题，即问题实例中包含较小的参数，因此固定参数算法为解决这些困难的计算问题提供了一个新的手段。近些年来，结构图论的重大突破和逻辑方法的广泛应用也使得固定参数算法和复杂性有了长足的发展。基于已有的工作我们的研究将集中于以下几个方面：1.通过发展有向图的结构理论和对应的逻辑理论，研究有向图上模型验证问题的参数复杂性和固定参数算法。2.子图同构问题的复杂性，尝试给出其完备的可解性刻画。同时研究其各变种的复杂性。3.各种图论问题的内核算法及其复杂性下界，以及其一般的逻辑刻画。

中文关键词： 参数复杂性；算法图论；可近似性；有限模型论；证明复杂性

英文摘要：

英文关键词： parameterized complexity；algorithmic graph theory；approximability；finite model theory；proof complexity