图上若干基本NP难问题的算法研究

项目名称： 图上若干基本NP难问题的算法研究

项目编号： No.60903007

项目类型： 青年科学基金项目

立项/批准年度： 2010

项目学科： 金属学与金属工艺

项目作者： 肖鸣宇

作者单位： 电子科技大学

项目金额： 18万元

中文摘要： 本项目主要从参数算法、精确算法和近似算法的角度来研究计算机中一些基本的图问题，其中包括被称之为六个基本NP难问题的独立集和点覆盖问题，以及经典的最大流最小割问题的扩展- - 图多分割问题。这些问题非常基础，且应用相当广泛，在整个计算机学科中影响深远，同时这些问题也被研究得非常透彻，任何改进都将在计算机学科内受到强烈关注。项目申请者在这些问题上具有较强的科研基础，近两年研究获得七个当前最优的参数算法、精确算法和近似算法，并解决一个近二十年的公开难题。 参数计算是本项目主要研究方法之一，研究的是一个很难的问题在某个参数较小的时候是否存在有效算法（参数算法）。基于申请人提出的最远最小割技术和新的分支理论，本项目将有望进一步改进并简化图多分割问题的参数算法，3度图及稀疏图上独立集和点覆盖问题的各项算法。在新理论下参数计算中另一个公开难题还有望被解决。目前以上科研进展顺利，预计3年完成。

中文关键词： NP-难问题；算法分析与设计；图论及图算法；参数算法；精确算法

英文摘要：

英文关键词： NP-hard Problems；Design & analysis of Alg.；Graph Algorithms；Parameterized Algorithms；Exact Algorithms