中文摘要：

申请者郭炅教授在参数算法和核心化算法及其应用等领域取得了卓越的成果，受到国际同行的好评与认可，发表了70多篇高质量论文，被广泛引用。根据Microsoft Academic Search (academic.research.microsoft.com)的最新统计（2011年3月2日），在过去五年中，郭炅教授在计算机理论和算法领域的Top Authors 中排名第十五位。近年来，申请者和合作者王建新教授在参数算法和核心化算法领域进行了多方面的合作，特别在对核心化算法设计技术的系统化上取得了初步的成绩。在此基础上，合作双方欲扩展和加深这方面的合作。具体的方向有（1）提出新的核心化算法的设计和分析方法；（2）改进一些重要问题的核心上限；（3）涉及针对结构参数的核心化算法；（4）研究核心化算法与别的算法的联系。通过本项目的实施将为难解问题提供新的算法预处理技术，推动相关领域的发展。

结论摘要：

在本基金的支持下，课题组对参数计算领域中核心化方法进行了系统研究，并对参数算法设计技术进行了深入的研究，取得了一系列的研究成果。在核心化算法的设计方面，通过对平面图结构的深入分析，提出了顶点划分技术，并将该技术应用到Connected Vertex Cover问题、Edge Dominating Set问题、Maximum Triangle Packing问题和Connected Dominating Set问题等核心化过程中，分别得到了大小分别为4k、12k、75k和130k的核，改进了当前的最好结果，14k、28k、624k和413k。在参数算法的设计方面，通过深入分析难解问题解空间的结构，分别对3种边删除问题以及两种边添加问题进行了研究，并相应地提出了改进的固定参数可解算法。此外，对于完美匹配图中顶点覆盖问题，提出了时间复杂度为O*(9^k)的参数算法，改进了之前最好的参数算法，其时间复杂度为O*(15^k)。在参数计算理论应用方面，将参数计算理论成功应用到了实际生活的诸多方面，如计算机网络、社会学以及生物信息学等。例如，对于无线自组网络中的Min-power multicast问题，证明了相关问题的参数复杂性，并提出了相关的参数算法。对于一些社会学中的难解问题，主要研究和分析了d-approval规则下Control，Manipulation和Bribery对投票的影响，并提出了相关的参数算法。此外，对生物信息学中的蛋白质复合物挖掘、网络基序发现和关键蛋白质预测等生物计算问题进行了深入的研究，并取得了一系列在国际上有影响的成果。此项目的研究不仅丰富和发展了参数计算理论及技术，同时也推动了用参数计算理论来各领域中的应用。