二部图上NP完全问题的研究

项目名称： 二部图上NP完全问题的研究

项目编号： No.61370052

项目类型： 面上项目

立项/批准年度： 2013

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

项目作者： 刘田

作者单位： 北京大学

项目金额： 73万元

中文摘要： 二部图是重要的图类，不仅可用来为实际问题建模，还可获得在一般图上难以获得的结论，其内部包含丰富的结构，可定义各种特殊的二部图，如凸二部图、环凸二部图、树凸二部图、弦二部图等。NP完全问题中有很多有实际应用但目前还缺乏多项式时间算法的计算问题，如最小顶点反馈集、最小联通支配集、最小独立支配集、哈密顿回路与通路等。这几个重要的计算问题在一般二部图上是NP完全的，在凸二部图上有多项式时间算法。本项目把凸二部图扩充到树凸二部图，并对相关的树施加不同限制，分别得到星凸二部图、三岔凸二部图等，在这些特殊的二部图上研究上述NP完全问题的算法和复杂度，确定对哪些图类有多项式时间算法及对哪些图类是NP完全的，对这些特殊的图类开展组合刻画、随机图、近似算法、参数算法、指数算法等方面的研究，目的是理解这些特殊二部图的数学结构对上述有重要应用的NP完全问题的算法设计的影响，为实际应用打下坚实的理论基础。

中文关键词： 二部图；NP完全；多项式时间；树凸二部图；圈凸二部图

英文摘要： Bipartite Graphs are an important class of graphs, not only of use in modelling practical problems, but also in obtaining results which are impossible for general graphs. There are a plenty of structures in bipartite graphs, and different kinds of special

英文关键词： Bipartite Graphs；NP-Complete；Polynomial-time；Tree Convex Bipartite Graphs；Circular Convex Bipartite Graphs