瓶颈斯坦纳树问题的计算复杂性与近似算法研究

基本信息
批准号:60603008
项目类别:青年科学基金项目
资助金额:25.00
负责人:李子茂
学科分类:
依托单位:中南民族大学
批准年份:2006
结题年份:2009
起止时间:2007-01-01 - 2009-12-31
项目状态: 已结题
项目参与者:王江晴,覃俊,唐菀,周凌云,张鹏
关键词:
近似性能比计算复杂性瓶颈Steiner树问题算法
结项摘要

重点研究瓶颈k-Steiner树问题在平面空间的近似计算复杂性,设计该问题近似性能比为1.414的多项式时间近似算法。研究具有实际意义、带限制条件的平面空间k-Steiner树问题的计算复杂性和多项式时间近似算法、精确算法。研究瓶颈k-Steiner树问题在字符串空间的计算复杂度,证明该问题为MAX-SNP难解;设计该问题在字符串空间的有效多项式时间近似算法。探讨最大边长度限定、寻求最少Steiner点的Steiner树问题的近似计算复杂度,证明该问题在平面空间和网格空间为MAX-SNP难解,设计该问题在平面空间和网格空间的近似性能比为2的多项式时间近似算法。本项目在无线通讯和波长分割多路转换光网设计、多设施定位设计、超大规模集成电路路由和生物演化树重建等领域具有重要的应用价值。

项目摘要

项目成果
{{index+1}}

{{i.achievement_title}}

{{i.achievement_title}}

DOI:{{i.doi}}
发表时间:{{i.publish_year}}

暂无此项成果

数据更新时间:2023-05-31

其他相关文献

1

基于铁路客流分配的旅客列车开行方案调整方法

基于铁路客流分配的旅客列车开行方案调整方法

DOI:
发表时间:2021
2

一种基于多层设计空间缩减策略的近似高维优化方法

一种基于多层设计空间缩减策略的近似高维优化方法

DOI:10.1051/jnwpu/20213920292
发表时间:2021
3

新型树启发式搜索算法的机器人路径规划

新型树启发式搜索算法的机器人路径规划

DOI:10.3778/j.issn.1002-8331.1903-0411
发表时间:2020
4

"多对多"模式下GEO卫星在轨加注任务规划

"多对多"模式下GEO卫星在轨加注任务规划

DOI:10.19328/j.cnki.2096-8655.2022.02.002
发表时间:2022
5

基于自适应干扰估测器的协作机器人关节速度波动抑制方法

基于自适应干扰估测器的协作机器人关节速度波动抑制方法

DOI:10.13973/j.cnki.robot.210412
发表时间:2022

李子茂的其他基金

相似国自然基金

1

网络连通控制集和斯坦纳树变形的近似算法

批准号:11026068
批准年份:2010
负责人:李宪越
学科分类:A0406
资助金额:3.00
项目类别:数学天元基金项目
2

斯坦纳树填装数猜想与图的树连通度

批准号:11601254
批准年份:2016
负责人:毛亚平
学科分类:A0409
资助金额:19.00
项目类别:青年科学基金项目
3

不相交QoS路径与斯坦纳网络的近似算法研究

批准号:61300025
批准年份:2013
负责人:郭龙坤
学科分类:F0201
资助金额:23.00
项目类别:青年科学基金项目
4

计算复杂性与近似算法

批准号:19331052
批准年份:1993
负责人:堵丁柱
学科分类:A0410
资助金额:8.00
项目类别:重点项目