计算复杂性的理论和应用
基本信息
批准号：19331050
项目类别：重点项目
资助金额：16.00
负责人：堵丁柱
学科分类：
依托单位：中国科学院数学与系统科学研究院
批准年份：1993
结题年份：1998
起止时间：1994-01-01 - 1998-12-31
项目状态： 已结题
项目参与者：胡晓东,李祥,黄文奇
关键词：
计算复杂性组合最优化近似算法
结项摘要
本项目关于计算复杂性的研究主要分为理论和应用两个方面。在理论部分，主要考虑基于制定时模型的计算复杂的问题。特别是验证了甲约斯特和维拉明猜想的正确性（n=6,10）。在应用部分，主要考虑的是最小斯坦纳树和，网络及其相关的网络优化设计问题，另外也探讨了克劳斯网络在多频率环境下的多种非阻塞性。主要结果分为网络的结构性分析和近似算法的设计。特别是分别证明了塞斯利克和格塞厄姆关于斯坦纳比的两个重要猜想。此外，分别堆翻了有关与斯密斯关于生成斯坦纳树的贪婪算法的猜想，同时推翻了厄尔伯特与鲍拉克斯坦纳比可以在正规单纯的上述到的猜想.
项目摘要
项目成果
{{index+1}}
{{i.achievement_title}}
{{i.achievement_title}}
DOI：{{i.doi}}
发表时间：{{i.publish_year}}
暂无此项成果
数据更新时间：2023-05-31
其他相关文献
1
小跨高比钢板- 混凝土组合连梁抗剪承载力计算方法研究
小跨高比钢板- 混凝土组合连梁抗剪承载力计算方法研究
DOI：10.19701/j.jzjg.2015.15.012
发表时间：2015
2
一种改进的多目标正余弦优化算法
一种改进的多目标正余弦优化算法
DOI：
发表时间：2019
3
多源数据驱动CNN-GRU模型的公交客流量分类预测
多源数据驱动CNN-GRU模型的公交客流量分类预测
DOI：10.19818/j.cnki.1671-1637.2021.05.022
发表时间：2021
4
基于混合优化方法的大口径主镜设计
基于混合优化方法的大口径主镜设计
DOI：10.3788/AOS202040.2212001
发表时间：2020
5
变可信度近似模型及其在复杂装备优化设计中的应用研究进展
变可信度近似模型及其在复杂装备优化设计中的应用研究进展
DOI：10.3901/jme.2020.24.219
发表时间：2020
堵丁柱的其他基金
批准号：18870493
批准年份：1988
资助金额：1.00
项目类别：面上项目
批准号：60573021
批准年份：2005
资助金额：22.00
项目类别：面上项目
批准号：19331052
批准年份：1993
资助金额：8.00
项目类别：重点项目
相似国自然基金
1
计算复杂性的理论和应用
批准号：19331051
批准年份：1993
负责人：黄文奇
学科分类：A0406
资助金额：4.00
项目类别：重点项目
2
装配型排序理论- - 计算复杂性、近似算法和随机算法
批准号：10371112
批准年份：2003
负责人：原晋江
学科分类：A0406
资助金额：17.00
项目类别：面上项目
3
量子计算复杂性理论专题讲习班
批准号：11926301
批准年份：2019
负责人：武俊德
学科分类：A0602
资助金额：20.00
项目类别：数学天元基金项目
4
多复变数Ｈp空间理论.拓扑与计算复杂性理论
批准号：18670495
批准年份：1986
负责人：史济怀
学科分类：A0208
资助金额：0.70
项目类别：面上项目