3-cactus上的连通p-median问题

• 作 者: 陈光亭 辛双 崔素辉
• 机 构: 杭州电子科技大学理学院运筹与控制研究所
• 出 处: 杭州电子科技大学学报
• 发表日期: 2010年2期
• 关键词: 选址问题 连通 导出子图 location problemconnected p-medianinduce subgraph
• 基金项目: 国家自然科学基金资助项目(60872093)

设G=(V,E)是一个无向连通图,每一条边e和每个顶点v都有一个非负的权重l(e)和w(v);传统的p-median是指在顶点集合中选出p个顶点,使得其它顶点到这p个顶点的赋权距离和最小。该文考虑带有某些约束的这类问题,要求所选出的p个顶点是连通的,也即由这p个顶点所导出的子图是连通的,称为连通p-median问题。该文给出了3-cactus图上的连通p-median问题的一个O(pn)的算法。