| 3-cactus上的连通p-median问题 |
| |
| 引用本文： | 陈光亭,辛双,崔素辉.3-cactus上的连通p-median问题[J].杭州电子科技大学学报,2010,30(2):77-80. |
| |
| 作者姓名： | 陈光亭 辛双 崔素辉 |
| |
| 作者单位： | 杭州电子科技大学理学院运筹与控制研究所,浙江,杭州,310018 |
| |
| 摘 要： | 设G=(V,E)是一个无向连通图,每一条边e和每个顶点v都有一个非负的权重l(e)和w(v);传统的p-median是指在顶点集合中选出p个顶点,使得其它顶点到这p个顶点的赋权距离和最小。该文考虑带有某些约束的这类问题,要求所选出的p个顶点是连通的,也即由这p个顶点所导出的子图是连通的,称为连通p-median问题。该文给出了3-cactus图上的连通p-median问题的一个O(pn)的算法。
|
| 关 键 词： | 选址问题 连通 导出子图 |
The Connected p-median Problem on the 3-cactus Graph |
| |
| CHEN Guang-ting,XIN Shuang,CUI Su-hui.The Connected p-median Problem on the 3-cactus Graph[J].Journal of Hangzhou Dianzi University,2010,30(2):77-80. |
| |
| Authors: | CHEN Guang-ting XIN Shuang CUI Su-hui |
| |
| Affiliation: | (Institute of Operational Research and Cybernetics,Hangzhou Dianzi University,Hangzhou Zhejiang 310018,China) |
| |
| Abstract: | 设G=(V,E)是一个无向连通图,每一条边e和每个顶点v都有一个非负的权重l(e)和w(v);传统的p-median是指在顶点集合中选出p个顶点,使得其它顶点到这p个顶点的赋权距离和最小。该文考虑带有某些约束的这类问题,要求所选出的p个顶点是连通的,也即由这p个顶点所导出的子图是连通的,称为连通p-median问题。该文给出了3-cactus图上的连通p-median问题的一个O(pn)的算法。 |
| |
| Keywords: | location problem connected p-median induce subgraph |
| 本文献已被 维普 万方数据 等数据库收录！ |
|
