项目名称: 可带负权的图的p-中心和p-中位问题

项目编号: No.10971131

项目类型: 面上项目

立项/批准年度: 2010

项目学科: 数理科学和化学

项目作者: 康丽英

作者单位: 上海大学

项目金额: 26万元

中文摘要: 图的中心和中位问题是图论与组合最优化理论研究的重要内容,它在选址、通讯、复杂网络和环境科学等领域中有着广泛的应用。与经典的中心和中位问题比较,国际上最近提出的可带负权的图的中心和中位问题在实际中更具有普遍意义。本项目侧重以图论和组合最优化为工具来开展对可带负权的图的中心和中位问题的研究,讨论其算法实现问题。研究的主要内容为:(1)在具有特殊结构的赋权图上,设计该类问题的多项式时间算法;(2)探索这些问题在一般赋权图上的近似算法实现。在研究方法上侧重图的结构性质的深入分析,并充分结合组合最优化方法,力争在理论方法上有新的突破。本课题将首次考虑该类问题的近似算法。对这些问题的研究,将推动图论、组合最优化、选址科学和复杂网络的交叉研究与发展,同时对一些实际问题的解决也具有一定的理论指导意义。

中文关键词: 赋权图;设施选址;中心;中位;算法

英文摘要:

英文关键词: Weighted graphs;facility location;center;median;algorithm

成为VIP会员查看完整内容
0

相关内容

【硬核书】机器人网络分布式控制
专知会员服务
67+阅读 · 2021年7月25日
【KDD2020】自适应多通道图卷积神经网络
专知会员服务
119+阅读 · 2020年7月9日
【人大】图实现算法综述与评测分析
专知会员服务
37+阅读 · 2020年4月28日
哪款应用的算法推荐让你觉得很准?
ZEALER订阅号
0+阅读 · 2022年4月9日
Apple:万亿美元收入指日可待
CSDN
0+阅读 · 2022年2月24日
腾讯 AI Lab 招图神经网络研究实习生,顶会带飞
图与推荐
1+阅读 · 2022年1月12日
NeurIPS 2021:半监督节点分类中的拓扑不平衡学习
图与推荐
1+阅读 · 2021年11月7日
周志华的《机器学习》西瓜书出全新视频课啦!
数据分析
16+阅读 · 2019年6月10日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
1+阅读 · 2008年12月31日
Arxiv
0+阅读 · 2022年4月17日
Heterogeneous Graph Transformer
Arxiv
27+阅读 · 2020年3月3日
Arxiv
23+阅读 · 2017年3月9日
小贴士
相关主题
相关基金
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
1+阅读 · 2008年12月31日
微信扫码咨询专知VIP会员