可带负权的图的p-中心和p-中位问题

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

项目编号： No.10971131

项目类型： 面上项目

立项/批准年度： 2010

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

项目作者： 康丽英

作者单位： 上海大学

项目金额： 26万元

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

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

英文摘要：

英文关键词： Weighted graphs；facility location；center；median；algorithm