固定参数可解算法在平面图问题的应用以及和整数线性规划的关系

项目名称： 固定参数可解算法在平面图问题的应用以及和整数线性规划的关系

项目编号： No.60973026

项目类型： 面上项目

立项/批准年度： 2010

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

项目作者： 鲁道夫

作者单位： 复旦大学

项目金额： 32万元

中文摘要： 这个项目属于理论计算机领域。我们计划研究固定参数可解算法以及内核算法在平面图问题上的应用。我们还计划要研究整数线性规划和固定参数可解算法之间的关系。我们将不仅从理论上给出界限的证明，还将从实验上探究现有的和一些新的算法的可行性。

中文关键词： 固定参数可解；FPT；内核算法；平面图；高效的算法

英文摘要：

英文关键词： fixed parameter tractable；FPT；kernelization；planar graph；efficient algorithm