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

图优化划分问题是图论与组合优化领域里的一个基础性问题，该问题要求将原图划分成顶点不交的p个部分，其中p>1，并对边集合进行调整（删除或添加）且满足相关的优化目标。由于其在生物信息、并行计算、大规模集成电路设计、数据挖掘、图像识别、以及大规模数据库的有效存储上都具有非常重要的应用，因此对该问题的研究在计算机科学领域里也占有极其重要的位置。大部分具有应用价值和理论背景的图优化划分问题都是NP完全问题。我们根据图优化划分问题的特性将其分成两大类型，着重选择了当前在生物信息领域具有应用背景和在理论上与染色问题相关的图优化划分问题,寻求全局优化性能、鲁棒性强、通用性强且适于并行处理的启发式算法和进行高近似程度的近似算法、随机算法的设计分析以及计算复杂性的研究。