图优化划分问题的算法和复杂性研究

项目名称： 图优化划分问题的算法和复杂性研究

项目编号： No.10801077

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

立项/批准年度： 2009

项目学科： 生物科学

项目作者： 张晓岩

作者单位： 南京师范大学

项目金额： 17万元

中文摘要： 图的划分问题是图论和组合优化的一个基础性问题，由于大部分具有应用价值和理论背景的图划分问题都是NP完全问题甚至是难近似问题，对于该问题的研究在计算机科学领域里也占有极其重要的位置。这类问题成为了数学与计算机科学相交叉领域中的重要和热点问题。图的划分问题将顶点集合或边的集合进行划分并达到目标的需求，比如针对顶点和边的划分的经典问题有染色问题或最大割问题、匹配问题等。这些问题中，有些问题在生物信息领域，比如基因调整网络和聚类划分等问题上有重要的应用价值；有些问题也可应用在算法博弈论中一个重要领域机制设计问题中；有些问题可以与有向Hamilton圈问题联系起来。围绕申请书的内容，项目申请者及其成员对有限制的超图最大割问题、单色和杂色圈划分问题、平面图线性染色问题、环面图的列表染色问题、二部图上的在线染色问题、图的导出匹配可扩问题等, 这些最大割、圈划分、匹配可扩、染色等边或顶点的划分问题在结构和算法以及复杂性方面进行了一系列的研究，取得了一些重要的进展和研究成果。在项目执行期间，项目申请者及其成员多次参加了国内外有关的学术会议，并与荷兰特文特大学应用数学系进行了学术的互访。

中文关键词： 图的划分;NP完全问题;结构性质；算法分析；复杂性分析

英文摘要： Graph partitioning problems are the basic problems in the area of graph theory and combinatorial optimization. As most of them are NP-complete problems, the issue of research in the field of computer science takes up an extreme position. Such kind of problems are also the important and hot ones in the intersection of mathematics and computer science. In general, the problems need to divide the graphs into the vertex-disjoint or edge-disjoint parts to meet their required goals. For example, the classical coloring problem, max cut problem and matching problem, etc. Some of the problems can be applied into the field of biological information and algrithmic game theory. Moreover, some can be connected with the directed Hamilon cycle problem. Up to now, we have obtained some important results on the structure properties and the analysis of algorithms and complexity for many graph partitioning problems. During the project implementation, the applicant and its members have participated in some related domestic and foreign academic conferences and conducted academic exchanges with the Department of Applied Mathematics, University of twente, in the Netherlands.

英文关键词： Graph partitioning;NP-complete problems;Structure properties;Analysis of algorithms; Complexity