图的中心(center)和中位(median) 问题是选址科学的两个核心问题，也是图论与组合最优化理论研究的重要内容，在通讯、复杂网络、运输和环境科学中有着广泛应用。国际上最近提出的可带负权的图的中心和中位问题在实际中更具有普遍意义。本项目侧重以图论和组合最优化为工具来开展对可带负权的图的中心和中位问题的研究，讨论了其算法实现问题。我们取得的主要成果如下：(1)关于p-maxian问题，讨论了对块图、区间图和仙人掌图几类图的p-maxian问题。对具有单位边长的块图p-maxian问题，证明了除3阶完全图外，块图的p-maxian问题是线性时间可解的；其次，给出了具有任意权区间图的p-maxian问题的线性时间算法；对区间图的任意权2-中位问题,若目标为MWD和WMD目标，分别给出了时间O(n2)的多项式算法；最后，我们证明了仙人掌图的2-maxian问题具有时间为O(n2)的多项式时间算法。(2)讨论了客户具有子图结构的可带负权p-中位问题，对具有单位边长块图的1-中位问题，若中位限制在图的顶点上，我们提出了该问题的一个线性时间算法；对客户具有子树结构的p-中位问题, 分别给出了树的1-中位问题和2-中位问题的多项式时间算法.（3）讨论了可带负权的p-中心问题的研究。p-中心问题是指在网络中放置p个设施，使得每个客户到达最近设施的最大权距离最小。证明了块图的无权1-中心问题是线性时间可解的。对服务设施以一定概率失效的选址问题，证明了区间图的备份2-中心问题是线性时间可解的。