重点研究瓶颈k-Steiner树问题在平面空间的近似计算复杂性,设计该问题近似性能比为1.414的多项式时间近似算法。研究具有实际意义、带限制条件的平面空间k-Steiner树问题的计算复杂性和多项式时间近似算法、精确算法。研究瓶颈k-Steiner树问题在字符串空间的计算复杂度,证明该问题为MAX-SNP难解;设计该问题在字符串空间的有效多项式时间近似算法。探讨最大边长度限定、寻求最少Steiner点的Steiner树问题的近似计算复杂度,证明该问题在平面空间和网格空间为MAX-SNP难解,设计该问题在平面空间和网格空间的近似性能比为2的多项式时间近似算法。本项目在无线通讯和波长分割多路转换光网设计、多设施定位设计、超大规模集成电路路由和生物演化树重建等领域具有重要的应用价值。
{{i.achievement_title}}
数据更新时间:2023-05-31
基于铁路客流分配的旅客列车开行方案调整方法
一种基于多层设计空间缩减策略的近似高维优化方法
新型树启发式搜索算法的机器人路径规划
"多对多"模式下GEO卫星在轨加注任务规划
基于自适应干扰估测器的协作机器人关节速度波动抑制方法
网络连通控制集和斯坦纳树变形的近似算法
斯坦纳树填装数猜想与图的树连通度
不相交QoS路径与斯坦纳网络的近似算法研究
计算复杂性与近似算法