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

基本信息
批准号:11026068
项目类别:数学天元基金项目
资助金额:3.00
负责人:李宪越
学科分类:
依托单位:兰州大学
批准年份:2010
结题年份:2011
起止时间:2011-01-01 - 2011-12-31
项目状态: 已结题
项目参与者:刘礼,蔡金转,李巍
关键词:
斯坦纳树单位圆盘图连通控制集近似算法
结项摘要

本项目主要研究网络上NP-完备最优化问题的近似算法,重点考察单位圆盘图上的连通控制集问题和斯坦纳树问题的变形。对于单位圆盘图上的连通控制集问题,本项目在已取得的研究成果的基础上,深入研究连通控制集和极大独立集之间的关系,并考察由MCDS生成区域的洞与MCDS大小之间的关系,希望改进现有算法的近似比,进而探索新的近似算法;本项目通过比较经典斯坦纳树问题及其变形之间的关系,以及不同斯坦纳树变形问题之间的关系来研究斯坦纳树变形问题的近似算法,特别将考虑internal斯坦纳树问题,提出更好更有效的近似算法。

项目摘要

项目成果
{{index+1}}

{{i.achievement_title}}

{{i.achievement_title}}

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

暂无此项成果

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

其他相关文献

1

针对弱边缘信息的左心室图像分割算法

针对弱边缘信息的左心室图像分割算法

DOI:10.3778/j.issn.1002-8331.1911-0012
发表时间:2020
2

基于被动变阻尼装置高层结构风振控制效果对比分析

基于被动变阻尼装置高层结构风振控制效果对比分析

DOI:10.13197/j.eeev.2019.05.95.fuwq.009
发表时间:2019
3

基于多色集合理论的医院异常工作流处理建模

基于多色集合理论的医院异常工作流处理建模

DOI:
发表时间:2020
4

新产品脱销等待时间对顾客抱怨行为的影响:基于有调节的双中介模型

新产品脱销等待时间对顾客抱怨行为的影响:基于有调节的双中介模型

DOI:
发表时间:2023
5

机电控制无级变速器执行机构动态响应特性仿真研究

机电控制无级变速器执行机构动态响应特性仿真研究

DOI:10.3969/j.issn.1004-132X.2020.03.001
发表时间:2020

李宪越的其他基金

批准号:11201208
批准年份:2012
资助金额:23.00
项目类别:青年科学基金项目

相似国自然基金

1

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

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

无线网络中连通控制集问题及其变形的近似算法的研究

批准号:11201208
批准年份:2012
负责人:李宪越
学科分类:A0406
资助金额:23.00
项目类别:青年科学基金项目
3

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

批准号:60603008
批准年份:2006
负责人:李子茂
学科分类:F0201
资助金额:25.00
项目类别:青年科学基金项目
4

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

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