图优化划分问题的算法和复杂性研究
批准号：
10801077
项目类别：
青年科学基金项目
资助金额：
17.0 万元
负责人：
张晓岩
依托单位：
学科分类：
图论及其应用
结题年份：
2011
批准年份：
2008
项目状态：
已结题
项目参与者：
董伟、张海辉、张化鹏、杨亦挺、张昊、李光暖
项目摘要
结项摘要
项目成果
张晓岩的其他基金
相似基金
相关文献
中文摘要
图优化划分问题是图论与组合优化领域里的一个基础性问题，该问题要求将原图划分成顶点不交的p个部分，其中p>1，并对边集合进行调整（删除或添加）且满足相关的优化目标。由于其在生物信息、并行计算、大规模集成电路设计、数据挖掘、图像识别、以及大规模数据库的有效存储上都具有非常重要的应用，因此对该问题的研究在计算机科学领域里也占有极其重要的位置。大部分具有应用价值和理论背景的图优化划分问题都是NP完全问题。我们根据图优化划分问题的特性将其分成两大类型，着重选择了当前在生物信息领域具有应用背景和在理论上与染色问题相关的图优化划分问题,寻求全局优化性能、鲁棒性强、通用性强且适于并行处理的启发式算法和进行高近似程度的近似算法、随机算法的设计分析以及计算复杂性的研究。
英文摘要
期刊论文列表
专著列表
科研奖励列表
会议论文列表
专利列表
登录
查看更多内容
DOI：
--
发表时间：
--
期刊：
中国科学:数学
影响因子：
--
作者：
[张晓岩, 许怡安]
通讯作者：
许怡安
Improved bounds on linear coloring of plane graphs
改进了平面图线性着色的界限
改进了平面图线性着色的界限
DOI：
10.1007/s11425-010-3073-0
发表时间：
2010-04
期刊：
Science China-Mathematics
影响因子：
1.4
作者：
[许宝刚, 董伟, 张晓岩]
通讯作者：
张晓岩
Minimum Size of n-Factor-Critical Graphs and k-Extendable Graphs
n 因子关键图和 k 可扩展图的最小大小
n 因子关键图和 k 可扩展图的最小大小
DOI：
10.1007/s00373-011-1045-y
发表时间：
2011-04
期刊：
Graphs and Combinatorics
影响因子：
0.7
作者：
[张晓岩, Zhang, Zan-Bo, Lou, Dingjun, Wen, Xuelian]
通讯作者：
Wen, Xuelian
DOI：
--
发表时间：
--
期刊：
Ars Combinatoria
影响因子：
作者：
[Li, Jing, Lu, Xiaoxu, 张晓岩, Zhang, Zan-Bo, ]
通讯作者：
VLSI中与信息网络相关的图优化算法研究
-
批准号：12271259
-
项目类别：面上项目
-
资助金额：46万元
-
批准年份：2022
-
负责人：张晓岩
-
依托单位：
芯片及网络设计中的图优化问题研究
-
批准号：11871280
-
项目类别：面上项目
-
资助金额：53.0万元
-
批准年份：2018
-
负责人：张晓岩
-
依托单位：
信息科学中图与超图划分问题的随机近似算法研究
-
批准号：11471003
-
项目类别：面上项目
-
资助金额：65.0万元
-
批准年份：2014
-
负责人：张晓岩
-
依托单位：
国内基金
海外基金