本项目主要研究网络上NP-完备最优化问题的近似算法,重点考察单位圆盘图上的连通控制集问题和斯坦纳树问题的变形。对于单位圆盘图上的连通控制集问题,本项目在已取得的研究成果的基础上,深入研究连通控制集和极大独立集之间的关系,并考察由MCDS生成区域的洞与MCDS大小之间的关系,希望改进现有算法的近似比,进而探索新的近似算法;本项目通过比较经典斯坦纳树问题及其变形之间的关系,以及不同斯坦纳树变形问题之间的关系来研究斯坦纳树变形问题的近似算法,特别将考虑internal斯坦纳树问题,提出更好更有效的近似算法。
{{i.achievement_title}}
数据更新时间:2023-05-31
针对弱边缘信息的左心室图像分割算法
基于被动变阻尼装置高层结构风振控制效果对比分析
基于多色集合理论的医院异常工作流处理建模
新产品脱销等待时间对顾客抱怨行为的影响:基于有调节的双中介模型
机电控制无级变速器执行机构动态响应特性仿真研究
斯坦纳树填装数猜想与图的树连通度
无线网络中连通控制集问题及其变形的近似算法的研究
瓶颈斯坦纳树问题的计算复杂性与近似算法研究
不相交QoS路径与斯坦纳网络的近似算法研究