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

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